| Lect | Date | Topic | Reference |
| | Linear Programming | |
| 1 |
08/29 |
Theory of LP |
[MG4, Go9] |
| 2 |
08/31 |
Simplex and Other Algorithms |
[MG5, Go10] |
| 3 |
09/05 |
Duality |
[MG6] |
| | Network Optimization | |
| 4 |
09/07 |
Min-Cut Max-Flow |
[KT7, Eri10] |
| 5 |
09/12 |
Max-Flow Algorithms |
[KT7, Eri10] |
| 6 |
09/14 |
Min-Cost Max Flow |
[Go, GT, Zw] |
| 7 |
09/19 |
Bipartite Matching & Optimal Transport |
[Rg, CP] |
| | Approximation Algorithms | |
| 8 |
09/21 |
Vertex Cover |
[KT11, WS7] |
| 9 |
09/26 |
Set Cover and Clustering |
[KT12, WS02] |
| 10 |
09/28 |
Clustering: k-means and Local Search |
[WS9] |
| 11 |
10/03 |
Multiplicative Weight Method |
[AHK] |
| 12 |
10/05 |
Primal-Dual Method |
[WS07] |
| Exam |
10/12 |
Midterm (Lectures 1-12) |
|
| | Randomized Algorithms | |
| 13 |
10/17 |
Expectation & Tail Bounds |
[KT13] |
| 14 |
10/19 |
Hashing |
[Eri-DC 5] |
| 15 |
10/24 |
Global Min-Cut |
[KT13] |
| 16 |
10/26 |
LP Rounding |
[KT13, WS5] |
| 17 |
10/31 |
SDP Rounding |
[WS6]
|
| | Similarity Search | |
| 18 |
11/02 |
Nearest-Neighbor Searching |
[HP11] |
| 19 |
11/07 |
Dimension Reduction |
[Mat15, BHK] |
| 20 |
11/09 |
Locality Sensitive Hashing |
[HP15] |
| 21 |
11/14 |
Sketching |
[CY3] |
| | Algebraic/Numerical Algorithms | |
| 22 |
11/16 |
Polynomial Identity Testing |
[MR7] |
| 23 |
11/21 |
Random Walk on Graphs |
[MR] |
| 24 |
11/28 |
Cheeger Inequality & Sparsest Cut |
[TBD] |
| 25 |
11/30 |
Spectral Clustering |
[TBD] |
| Exam |
12/05 |
Midterm 2 (Lectures 13-25)
|
|