## 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)
;
Derry, A. (TA)
;
Machiraju, G. (TA)
...
more instructors for BIOE 214 »

## 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)
;
Machiraju, G. (TA)
...
more instructors for BIOMEDIN 214 »

## CME 251: Geometric and Topological Data Analysis (CS 233)

Mathematical and computational tools for the analysis of data with geometric content, such images, videos, 3D scans, GPS traces -- as well as for other data embedded into geometric spaces. Global and local geometry descriptors allowing for various kinds of invariances. The rudiments of computational topology and persistent homology on sampled spaces. Clustering and other unsupervised techniques. Spectral methods for graph data. Linear and non-linear dimensionality reduction techniques. Alignment, matching, and map computation between geometric data sets. Function spaces and functional maps. Networks of data sets and joint analysis for segmentation and labeling. Deep learning on irregular geometric data. Prerequisites: discrete algorithms at the level of
CS161; linear algebra at the level of Math51 or
CME103.

Terms: Spr
| Units: 3

Instructors:
Guibas, L. (PI)

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

Instructors:
Anari, N. (PI)
;
Charikar, M. (PI)
;
Rubinstein, A. (PI)
;
Kautz, W. (TA)
;
Liu, P. (TA)
;
Miller, L. (TA)
;
Qu, J. (TA)
;
Zuo, A. (TA)

## CS 161A: Problem-Solving Lab for CS161

Additional problem solving practice for
CS161. Sections are designed to allow students to acquire a deeper understanding of CS and its applications, work collaboratively, and develop a mastery of the material. Concurrent enrollment in
CS 161 required. Limited enrollment, permission of instructor, and application required.

Terms: Aut
| Units: 1

Instructors:
Rubinstein, A. (PI)
;
Wang, A. (TA)

## CS 163: The Practice of Theory Research

(Previously numbered
CS 353). Introduction to research in the Theory of Computing, with an emphasis on research methods (the practice of research), rather than on any particular body of knowledge. The students will participate in a highly structured research project: starting from reading research papers from a critical point of view and conducting bibliography searches, through suggesting new research directions, identifying relevant technical areas, and finally producing and communicating new insights. The course will accompany the projects with basic insights on the main ingredients of research. Research experience is not required, but basic theory knowledge and mathematical maturity are expected. The target participants are advanced undergrads as well as MS students with interest in CS theory. Prerequisites: CS161 and
CS154. Limited class size.

Terms: Win
| Units: 3
| UG Reqs: WAY-SMA

Instructors:
Reingold, O. (PI)

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

Instructors:
Schwarz, K. (PI)

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

## CS 233: Geometric and Topological Data Analysis (CME 251)

Mathematical and computational tools for the analysis of data with geometric content, such images, videos, 3D scans, GPS traces -- as well as for other data embedded into geometric spaces. Global and local geometry descriptors allowing for various kinds of invariances. The rudiments of computational topology and persistent homology on sampled spaces. Clustering and other unsupervised techniques. Spectral methods for graph data. Linear and non-linear dimensionality reduction techniques. Alignment, matching, and map computation between geometric data sets. Function spaces and functional maps. Networks of data sets and joint analysis for segmentation and labeling. Deep learning on irregular geometric data. Prerequisites: discrete algorithms at the level of
CS161; linear algebra at the level of Math51 or
CME103.

Terms: Spr
| Units: 3

Instructors:
Guibas, L. (PI)

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

Last offered: Winter 2020

Filter Results: