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

- Probability and Computing, by Mitzenmacher and Upfal
- The Design of Approximation Algorithms, by Williamson and Shmoys
- Notes on Spectral Graph Theory by Dan Spielman.