LEC # | TOPICS | LECTURE NOTES |
---|---|---|
1 | Introduction | No notes for Lecture 1 |
2 | Linear programming (LP): basic notions, simplex method | (PDF) (Courtesy of Alice Oh. Used with permission.) |
3 | LP: Farkas Lemma, duality | (PDF) (Courtesy of Abhinav Kumar and Nodari Sitchinava. Used with permission.) |
4 | LP: complexity issues, ellipsoid method | (PDF) (Courtesy of Reina Riemann. Used with permission.) |
5 | LP: ellipsoid method | (PDF) (Courtesy of Dennis Quan. Used with permission.) |
6 | LP: optimization vs. separation, interior-point algorithm | (PDF) (Courtesy of Bin Song and Hanson Zhou. Used with permission.) |
7 | LP: optimality conditions, interior-point algorithm (analysis) | (PDF) (Courtesy of Nick Hanssens and Nicholas Matsakis. Used with permission.) |
8 |
LP: interior-point algorithm wrap up Network flows (NF) | (PDF) (Courtesy of Jelena Spasojevic. Used with permission.) |
9 | NF: Min-cost circulation problem (MCCP) | (PDF) (Courtesy of Jasper Lin. Used with permission.) |
10 | NF: cycle cancelling algs for MCCP | (PDF) (Courtesy of Ashish Koul. Used with permission.) |
11 | NF: Goldberg-Tarjan alg for MCCP and analysis | (PDF) (Courtesy of Mohammad Hajiaghayi and Vahab Mirrokni. Used with permission.) |
12 |
NF: cancel-and-tighten Data structures (DS): Binary search trees | (PDF) (Courtesy of David Woodruff and Xiaowen Xin. Used with permission.) |
13 | DS: Splay trees, amortized analysis, dynamic tree | (PDF) (Courtesy of Naveen Sunkavally. Used with permission.) |
14 | DS: dynamic tree operations | (PDF) (Courtesy of Sanmay Das. Used with permission.) |
15 |
DS: analysis of dynamic trees NF: use of dynamic trees for cancel-and-tighten | (PDF) (Courtesy of Timothy Danford. Used with permission.) |
16 | Approximation algorithms (AA): hardness, inapproximability, analysis of approximation algorithms | (PDF) (Courtesy of Nicole Immorlica and Mana Taghdiri. Used with permission.) |
17 | AA: vertex cover (rounding, primal-dual), generalized Steiner tree | (PDF) (Courtesy of Matt Peters and Steven Richman. Used with permission.) |
18 | AA: primal-dual alg for generalized Steiner tree | (PDF) (Courtesy of Johnny Chen and Ahmed Ismail. Used with permission.) |
19 | AA: derandomization | (PDF) (Courtesy of Shalini Agarwal and Shane Swenson. Used with permission.) |
20 | AA: MAXCUT, SDP-based 0.878-approximation algorithm | (PDF 1.2 MB) (Courtesy of William Theis and David Liben-Nowell. Used with permission.) |
21 | AA: polynomial approximation schemes, scheduling problem: P||Cmax | (PDF) |
22 | AA: approximation Scheme for Euclidean TSP | (PDF - 1.2 MB)* (Courtesy of Salil Vadhan (Thomas D. Cabot Associate Professor of Computer Science). Used with permission.) |
23 | AA: multicommodity flows and cuts and embeddings of metrics | (PDF - 7.2 MB)** |