## BIOE 214: Representations and Algorithms for Computational Molecular Biology (BIOMEDIN 214, CS 274, GENE 214)

Topics: introduction to bioinformatics and computational biology, algorithms for alignment of biological sequences and structures, computing with strings, phylogenetic tree construction, hidden Markov models, basic structural computations on proteins, protein structure prediction, protein threading techniques, homology modeling, molecular dynamics and energy minimization, statistical analysis of 3D biological data, integration of data sources, knowledge representation and controlled terminologies for molecular biology, microarray analysis, machine learning (clustering and classification), and natural language text processing. Prerequisite:
CS 106B; recommended:
CS161; consent of instructor for 3 units.

Terms: Aut
| Units: 3-4

Instructors:
Altman, R. (PI)
;
Ferraro, N. (TA)
;
Flynn, E. (TA)
...
more instructors for BIOE 214 »

Instructors:
Altman, R. (PI)
;
Ferraro, N. (TA)
;
Flynn, E. (TA)
;
Lavertu, A. (TA)
;
Marafino, B. (TA)

## BIOMEDIN 214: Representations and Algorithms for Computational Molecular Biology (BIOE 214, CS 274, GENE 214)

Topics: introduction to bioinformatics and computational biology, algorithms for alignment of biological sequences and structures, computing with strings, phylogenetic tree construction, hidden Markov models, basic structural computations on proteins, protein structure prediction, protein threading techniques, homology modeling, molecular dynamics and energy minimization, statistical analysis of 3D biological data, integration of data sources, knowledge representation and controlled terminologies for molecular biology, microarray analysis, machine learning (clustering and classification), and natural language text processing. Prerequisite:
CS 106B; recommended:
CS161; consent of instructor for 3 units.

Terms: Aut
| Units: 3-4

Instructors:
Altman, R. (PI)
;
Ferraro, N. (TA)
;
Flynn, E. (TA)
...
more instructors for BIOMEDIN 214 »

Instructors:
Altman, R. (PI)
;
Ferraro, N. (TA)
;
Flynn, E. (TA)
;
Lavertu, A. (TA)
;
Marafino, B. (TA)

## CS 161: Design and Analysis of Algorithms

Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching. Prerequisite: 103 or 103B; 109 or
STATS 116.

Terms: Aut, Win, Sum
| Units: 3-5
| UG Reqs: GER:DB-EngrAppSci, WAY-FR

Instructors:
Eng, D. (PI)
;
Guibas, L. (PI)
;
Wootters, M. (PI)
;
Blaine, E. (TA)
;
Chatziafratis, V. (TA)
;
Chen, J. (TA)
;
Chen, M. (TA)
;
Chen, S. (TA)
;
Chen, W. (TA)
;
Corcoran, B. (TA)
;
Diana, E. (TA)
;
Gabrielsson, R. (TA)
;
Gan, E. (TA)
;
Garcia, A. (TA)
;
Hancock, B. (TA)
;
Hong, J. (TA)
;
Hu, S. (TA)
;
Khandwala, N. (TA)
;
Kim, S. (TA)
;
Murphy, D. (TA)
;
Paskov, I. (TA)
;
Redondo, E. (TA)
;
Rong, K. (TA)
;
Su, J. (TA)
;
Vu, A. (TA)
;
Warshaw, D. (TA)
;
Wright, D. (TA)
;
Wu, X. (TA)

## CS 166: Data Structures

Techniques in the design, analysis, and implementation of data structures. Isometries between data structures (including red/black trees and 2-3-4 trees), amortized analysis (including Fibonacci heaps and splay trees), and randomization (including count-min sketches and dynamic perfect hash tables). Data structures for integers and strings (including van Emde Boas trees and suffix trees). Possible additional topics include functional data structures, concurrent data structures, and spatial data structures. Prerequisites: CS107 and
CS161.

Terms: Spr
| Units: 3-4

Instructors:
Schwarz, K. (PI)
;
Douglass, M. (TA)
;
Musa, R. (TA)
;
Plaut, B. (TA)
;
Redmond, S. (TA)

## CS 168: The Modern Algorithmic Toolbox

This course will provide a rigorous and hands-on introduction to the central ideas and algorithms that constitute the core of the modern algorithms toolkit. Emphasis will be on understanding the high-level theoretical intuitions and principles underlying the algorithms we discuss, as well as developing a concrete understanding of when and how to implement and apply the algorithms. The course will be structured as a sequence of one-week investigations; each week will introduce one algorithmic idea, and discuss the motivation, theoretical underpinning, and practical applications of that algorithmic idea. Each topic will be accompanied by a mini-project in which students will be guided through a practical application of the ideas of the week. Topics include hashing, dimension reduction and LSH, boosting, linear programming, gradient descent, sampling and estimation, and an introduction to spectral techniques. Prerequisites: CS107 and
CS161, or permission from the instructor.

Terms: Spr
| Units: 3-4

Instructors:
Valiant, G. (PI)
;
Katzman, M. (TA)
;
Mussmann, S. (TA)
...
more instructors for CS 168 »

Instructors:
Valiant, G. (PI)
;
Katzman, M. (TA)
;
Mussmann, S. (TA)
;
Sharan, V. (TA)
;
Suksompong, W. (TA)

## CS 264: Beyond Worst-Case Analysis

This course is motivated by problems for which the traditional worst-case analysis of algorithms fails to differentiate meaningfully between different solutions, or recommends an intuitively "wrong" solution over the "right" one. This course studies systematically alternatives to traditional worst-case analysis that nevertheless enable rigorous and robust guarantees on the performance of an algorithm. Topics include: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models. Motivating problems will be drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, machine learning, and auction theory. Prerequisites:
CS161 (required). CS261 is recommended but not required.

Last offered: Winter 2017

## CS 269I: Incentives in Computer Science

Many 21st-century computer science applications require the design of software or systems that interact with multiple self-interested participants. This course will provide students with the vocabulary and modeling tools to reason about such design problems. Emphasis will be on understanding basic economic and game theoretic concepts that are relevant across many application domains, and on case studies that demonstrate how to apply these concepts to real-world design problems. Topics include auction and contest design, equilibrium analysis, cryptocurrencies, design of networks and network protocols, reputation systems, social choice, and social network analysis. Case studies include BGP routing, Bitcoin, eBay's reputation system, Facebook's advertising mechanism, Mechanical Turk, and dynamic pricing in Uber/Lyft. Prerequisites:
CS106B/X and
CS161, or permission from the instructor.

Last offered: Autumn 2016

## CS 274: Representations and Algorithms for Computational Molecular Biology (BIOE 214, BIOMEDIN 214, GENE 214)

Topics: introduction to bioinformatics and computational biology, algorithms for alignment of biological sequences and structures, computing with strings, phylogenetic tree construction, hidden Markov models, basic structural computations on proteins, protein structure prediction, protein threading techniques, homology modeling, molecular dynamics and energy minimization, statistical analysis of 3D biological data, integration of data sources, knowledge representation and controlled terminologies for molecular biology, microarray analysis, machine learning (clustering and classification), and natural language text processing. Prerequisite:
CS 106B; recommended:
CS161; consent of instructor for 3 units.

Terms: Aut
| Units: 3-4

Instructors:
Altman, R. (PI)
;
Ferraro, N. (TA)
;
Flynn, E. (TA)
;
Lavertu, A. (TA)
;
Marafino, B. (TA)

## GENE 214: Representations and Algorithms for Computational Molecular Biology (BIOE 214, BIOMEDIN 214, CS 274)

Terms: Aut
| Units: 3-4

Instructors:
Altman, R. (PI)
;
Ferraro, N. (TA)
;
Flynn, E. (TA)
...
more instructors for GENE 214 »

## IMMUNOL 207: Essential Methods in Computational and Systems Immunology

Introduction to the major underpinnings of systems immunology: first principles of development of computational approaches to immunological questions and research; details of the algorithms and statistical principles underlying commonly used tools; aspects of study design and analysis of data sets. Prerequisites: CS106a and CS161 strongly recommended.

Terms: Spr
| Units: 3

Filter Results: