Lect | Date | Topic | Reference |
| | Linear Programming | |
1 |
08/26 |
Theory of LP |
[MG 4, Go 9] |
2 |
08/28 |
Simplex and Other Algorithms |
[MG 5, Go 10] |
3 |
09/02 |
Duality |
[MG 6] |
4 |
09/04 |
Multiplicative Weight Method |
[MG 7, Cla] |
| | Network Optimization | |
5 |
09/09 |
Min-Cut Max-Flow |
[KT 7, Eri 10] |
6 |
09/11 |
Max-Flow Algorithms |
[KT 7, Eri 10] |
7 |
09/16 |
Bipartite Matching |
[KT 7, HK] |
8 |
09/20 |
Min-Cost Max Flow |
[Kar, GT] |
| | Approximation Algorithms | |
9 |
09/23 |
Vertex Cover and Set Cover |
[KT 11] |
10 |
09/25 |
Clustering |
[KT 12, WS 02] |
11 |
09/30 |
Facility Location |
[WS 09] |
12 |
10/02 |
Primal-Dual Method |
[WS 07] |
Exam |
10/09 |
Midterm (Lectures 1-12) |
|
| | Randomized Algorithms | |
13 |
10/14 |
Expectation & Tail Bounds |
[KT 13] |
14 |
10/16 |
Universal Hashing |
[Eri-DC 5] |
15 |
10/21 |
Hashing & Bloom Filters |
[Eri-DC 5, BM] |
16 |
10/23 |
LP Rounding |
[KT 13, WS 5] |
17 |
10/28 |
Global Min-Cut |
[KT 13]
|
| | Similarity Search | |
18 |
10/30 |
Nearest-Neighbor Searching |
[HP 11] |
19 |
11/04 |
Dimension Reduction |
[Mat 15, BHK] |
20 |
11/06 |
Locality Sensitive Hashing |
[HP 15] |
21 |
11/11 |
Sketching |
[CY 3] |
| | Algebraic/Numerical Algorithms | |
22 |
11/13 |
Polynomial Identity Testing |
[MR 7] |
23 |
11/18 |
Spectral Graph Theory |
[Lux, RV] |
24 |
11/20 |
Spectral Graph Theory |
[Lux, RV] |
25 |
11/25 |
Spectral Clustering |
[BP] |
Exam |
12/04 |
Midterm 2 (Lectures 13-25)
|
|