Courses:

The students in this course were required to take turns scribing lecture notes. They were provided with detailed instructions and a template. The process of scribing lecture notes provides students with valuable experience preparing mathematical documents, and also generates a useful set of lecture notes for the class.

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

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