## 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

## 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)
;
Derry, A. (TA)
;
Guo, M. (TA)
...
more instructors for BIOMEDIN 214 »

## 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:
Rubinstein, A. (PI)
;
Shi, K. (PI)
;
Wootters, M. (PI)
...
more instructors for CS 161 »

Instructors:
Rubinstein, A. (PI)
;
Shi, K. (PI)
;
Wootters, M. (PI)
;
Cai, B. (TA)
;
Hosgur, H. (TA)
;
Jones, E. (TA)
;
Lin, D. (TA)
;
Manoj, N. (TA)
;
Miller, L. (TA)
;
Mosse, M. (TA)
;
Portilheiro, V. (TA)
;
Qu, J. (TA)
;
Ramakrishnan, P. (TA)
;
Ramseyer, G. (TA)
;
Sawhney, A. (TA)
;
Shi, K. (TA)
;
Spayd, J. (TA)
;
Stanford-Moore, A. (TA)
;
Vitko, A. (TA)
;
Zhu, K. (TA)
;
Zhuk, W. (TA)
;
Zuo, A. (TA)

## CS 166: Data Structures

This course is designed as a deep dive into the design, analysis, implementation, and theory of data structures. Over the course of the quarter, we'll explore fundamental techniques in data structure design (isometries, amortization, randomization, word-level parallelism, etc.). In doing so, we'll see a number of classic data structures like Fibonacci heaps and suffix trees as well as more modern data structures like count-min sketches and range minimum queries. By the time we've finished, we'll have seen some truly beautiful strategies for solving problems efficiently. Prerequisites: CS107 and
CS161.

Terms: Spr
| Units: 3-4

## 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)
;
Barratt, J. (TA)
;
Cohen-Wang, B. (TA)
...
more instructors for CS 168 »

Instructors:
Valiant, G. (PI)
;
Barratt, J. (TA)
;
Cohen-Wang, B. (TA)
;
Guan, M. (TA)
;
Gupta, N. (TA)
;
Qiao, M. (TA)
;
Ramakrishnan, P. (TA)
;
Wang, W. (TA)

## CS 260: Geometry of Polynomials in Algorithm Design

Over the years, many powerful algorithms have been built via tools such as linear programming relaxations, spectral properties of graphs, and others, that all bridge the discrete and continuous worlds. This course will cover another such tool recently gaining popularity: polynomials, their roots, and their analytic properties, collectively known as geometry of polynomials. The course will cover fundamental properties of polynomials that are useful in designing algorithms, and then will showcase applications in several areas of algorithm design: combinatorial optimization, graph sparsification, high-dimensional expanders, analysis of random walks on combinatorial objects, and counting algorithms. Prerequisites: CS161 or equivalent. Basic knowledge of probability, linear algebra, and calculus.

Terms: Win
| Units: 3

Instructors:
Ahmadipouranari, N. (PI)

## 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 268: Geometric Algorithms

Techniques for design and analysis of efficient geometric algorithms for objects in 2-, 3-, and higher dimensions. Topics: convexity, triangulations and simplicial complexes, sweeping, partitioning, and point location. Voronoi/Delaunay diagrams and their properties. Arrangements of curves and surfaces. Intersection and visibility problems. Geometric searching and optimization. Random sampling methods. Range searching. Impact of numerical issues in geometric computation. Example applications to robotic motion planning, visibility preprocessing and rendering in graphics, and model-based recognition in computer vision. Prerequisite: discrete algorithms at the level of
CS161. Recommended:
CS164.

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

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

Terms: Aut
| Units: 3-4

Filter Results: