Courses:

Advanced Algorithms >> Content Detail



Lecture Notes



Lecture Notes

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 #TOPICSLECTURE NOTES
1IntroductionNo notes for Lecture 1
2

LINEAR PROGRAMMING (LP): basic notions, simplex method

(PDF) (Courtesy of Alice Oh. Used with permission.)
3LP: Farkas Lemma, duality(PDF) (Courtesy of Abhinav Kumar and Nodari Sitchinava. Used with permission.)
4LP: complexity issues, ellipsoid method(PDF) (Courtesy of Reina Riemann. Used with permission.)
5LP: ellipsoid method(PDF) (Courtesy of Dennis Quan. Used with permission.)
6LP: optimization vs. separation, interior-point algorithm(PDF) (Courtesy of Bin Song and Hanson Zhou. Used with permission.)
7LP: 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.)
9NF: Min-cost circulation problem (MCCP)(PDF) (Courtesy of Jasper Lin. Used with permission.)
10NF: Cycle cancelling algs for MCCP(PDF) (Courtesy of Ashish Koul. Used with permission.)
11NF: 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.)
13DS: Splay trees, amortized analysis, dynamic tree(PDF) (Courtesy of Naveen Sunkavally. Used with permission.)
14DS: 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.)
16APPROXIMATION ALGORITHMS (AA): hardness, inapproximability, analysis of approximation algorithms(PDF) (Courtesy of Nicole Immorlica and Mana Taghdiri. Used with permission.)
17AA: Vertex cover (rounding, primal-dual), generalized Steiner tree(PDF) (Courtesy of Matt Peters and Steven Richman. Used with permission.)
18AA: Primal-dual alg for generalized Steiner tree(PDF) (Courtesy of Johnny Chen and Ahmed Ismail. Used with permission.)
19AA: Derandomization(PDF) (Courtesy of Shalini Agarwal and Shane Swenson. Used with permission.)
20AA: MAXCUT, SDP-based 0.878-approximation algorithm(PDF) (Courtesy of William Theis and David Liben-Nowell. Used with permission.)
21AA: Polynomial approximation schemes, scheduling problem: P||Cmax (PDF)
22AA: Approximation Scheme for Euclidean TSP(PDF)* (Courtesy of Salil Vadhan (Thomas D. Cabot Associate Professor of Computer Science). Used with permission.)
23AA: 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.

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.