## 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. Linear and non-linear dimensionality reduction techniques. Graph representations of data and spectral methods. The rudiments of computational topology and persistent homology on sampled spaces, with applications. Global and local geometry descriptors allowing for various kinds of invariances. Alignment, matching, and map/correspondence computation between geometric data sets. Annotation tools for geometric data. Geometric deep learning on graphs and sets. Function spaces and functional maps. Networks of data sets and joint learning for segmentation and labeling. 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 145: Introduction to Big Data Systems

Introduction to the use, design, and implementation of database and data-intensive systems, including data models; schema design; data storage; query processing, query optimization, and cost estimation; concurrency control, transactions, and failure recovery; distributed and parallel execution; semi-structured databases; and data system support for advanced analytics and machine learning. Prereqs: CS106B or
CS106X;
CS103. Need to have a basic understanding of RAM, disks, sorting/hashing algorithms. Soft prereqs: One of CS161 or
CS111.

Terms: Aut
| Units: 3-4
| UG Reqs: GER:DB-EngrAppSci

## 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: 106B or 106X; 103 or 103B; 109 or
STATS 116.

Terms: Aut, Win
| 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)
;
Santiago, F. (TA)
;
Wang, A. (TA)

## CS 161ACE: 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, Win
| Units: 1

Instructors:
Villescas, M. (PI)

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

Last offered: Winter 2022
| UG Reqs: WAY-SMA

## CS 166: Data Structures

This course is a deep dive into the design, analysis, implementation,nand theory of data structures. Over the course of the quarter, we'llnexplore fundamental techniques in data structure design (isometries,namortization, randomization, etc.) and explore perspectives andnintuitions useful for developing new data structures. We'll do so bynsurveying classic data structures like Fibonacci heaps and suffix trees,nas well as more modern data structures like count-min sketches and rangenminimum queries. By the time we've finished, we'll have seen some trulynbeautiful strategies for solving problems efficiently. Prerequisites:nCS107 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 194: Software Project

Design, specification, coding, and testing of a significant team programming project under faculty supervision. Documentation includes capture of project rationale, design and discussion of key performance indicators, a weekly progress log and a software architecture diagram. Public demonstration of the project at the end of the quarter. Preference given to seniors. May be repeated for credit. Prerequisites: CS109 and
CS161.

Terms: Win, Spr
| Units: 3
| Repeatable
for credit

Instructors:
Borenstein, J. (PI)

## CS 194W: Software Project (WIM)

Restricted to Computer Science and Electrical Engineering undergraduates. Writing-intensive version of
CS194. Preference given to seniors. Prerequisites: CS109 and
CS161.

Terms: Win, Spr
| Units: 3

Instructors:
Borenstein, J. (PI)

## CS 210A: Software Project Experience with Corporate Partners

Two-quarter project course. Focus is on real-world software development. Corporate partners seed projects with loosely defined challenges from their R&D labs; students innovate to build their own compelling software solutions. Student teams are treated as start-up companies with a budget and a technical advisory board comprised of instructional staff and corporate liaisons. Teams will typically travel to the corporate headquarters of their collaborating partner, meaning some teams will travel internationally. Open loft classroom format such as found in Silicon Valley software companies. Exposure to: current practices in software engineering; techniques for stimulating innovation; significant development experience with creative freedoms; working in groups; real-world software engineering challenges; public presentation of technical work; creating written descriptions of technical work. Prerequisites: CS109 and
CS161.

Terms: Win
| Units: 3-4

Instructors:
Borenstein, J. (PI)

Filter Results: