Lectures

LectDateTopicReference
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)

home | page top