CS270: Combinatorial Algorithms and Data Structures
This is an introductory graduate course on algorithm design for students in computer science, engineering, or mathematics.
| Lecture: |
Tuesdays 12:30-2:00 Soda 306 and Thursdays 12:30-2:00
Soda 306
|
| Instructor: |
Lap Chi Lau |
| Office hours: |
Tuesdays 2:30-3:30 Soda 665 and Wednesdays 2:30-3:30 Soda
665 |
| Tutor: |
Tselil Schramm |
| TA office hours: |
Thursdays 5:30-6:30 Soda 615 |
We will study modern techniques in algorithmic design, including probabilistic techniques, optimization techniques and linear algebraic techniques.
- Randomized Algorithms - Probabilistic tools have become indispensible in algorithm design.
- Chernoff bounds, graph sparsification.
- balls and bins, hashing, data streaming.
- probabilistic methods, local lemma.
- random walks, Markov chain Monte Carlo.
- Schwartz-Zippel, network coding.
- Linear and Semidefinite Programming - A general and powerful approach for combinatorial optimization and approximation algorithms.
- linear programming, iterative rounding.
- semidefinite programming, randomized rounding.
- duality theorems, primal-dual methods, multiplicative update methods.
- Spectral Analysis - We will study how eigenvalues and eigenvectors can be used to design and analyze algorithms, from graph partitioning to random walks to solving linear equations.
- spectral graph theory, Cheeger's inequality, small-set expansion.
- electrical networks, random walks, spectral sparsifier.
- convex optimization, Laplacian solver, maximum flow.
References: Notes will be provided. See my previous notes on (randomness), (LP), (SDP), and (spectral) to get a good idea of the topics to come.
See also the previous offerings of CS270 by Prof. Satish Rao (2013) (2012). The following is a list of main references; see the project page for more references.