Study Materials

Lecture notes from previous years are included below. While they do not follow the current schedule, these are still good resources for the course.

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

* There were no scribe notes for this lecture for the Fall 2001 term. The notes from a previous term cover the same topic and are linked here.

** There were no scribe notes for this lecture for the Fall 2001 term. Section 8 of the notes from a previous term cover the same topic and are linked here.

Linear Programming (PDF - 5.1 MB)

Network Flows (PDF - 3.1 MB)

Approximation Algorithms (PDF - 7.2 MB)

The lecture notes below were provided by students who took the class in an earlier term:

  • A Simple Mincut Algorithm (PDF) (Courtesy of Roberto De Prisco (Associate Professor at the University of Salerno, Italy). Used with permission.)
  • Euclidean TSP Approximation Scheme (PDF - 1.2 MB) (Courtesy of Salil Vadhan (Thomas D. Cabot Associate Professor of Computer Science). Used with permission.)
  • Lattices (PDF - 2.2 MB) (Courtesy of David Wilson. Used with permission.)