Readings

• Lecture 1 (Stable Matchings): Section 1.1, Section 2.3 and Solved Exercise 2.
• Lecture 2 (Dynamic Programming): Section 6.1, Section 6.2 and Section 6.4. Do brush up on Section 2.2 for a refresher on asymptotic analysis.
• Lecture 3 (Shortest Paths): Section 6.8, Section 6.10.
• Lecture 4 (Greedy Algorithms: Caching, Minimum Spanning Tree): Section 4.3, Section 4.5.
• Lecture 5 (Greedy Algorithms: Minimum Spanning Tree, Matroid): Section 16.4 from CLRS.
• Lecture 6 (Randomized Algorithms: Global Min-Cut): Section 13.2.
• Lecture 7 (Randomized Algorithms: Online Algorithms: Caching): 13.8
• Lecture 8 (Linear Programming, Max Flow): Secion 29.1,29.2,29.4 CLRS, Section 7.1, Section 7.2 (KT)
• Lecture 9 (Max-Flow Min-Cut Theorem, LP duality): Section 29.2, Section 29.4 (Exercises 29.4.1,29.4.2, 29.4.5)
• Lecture 10 (Max-Flow Min-Cut Algorithms): Section 7.1 (KT) and Section 26.2 (CLRS).
• Lecture 11 (Max-Flow Min Cut Application): Section 7.5, 7.6, 7.7, 7.8,7.9,7.12. Slides by Kevin Wanye.
• Lecture 12 (Simplex Method): Section 29.3 CLRS.
• Lecture 13 (Fundamental Theorem of Linear Programming): Section 29.4, 29.5 (CLRS).
• Lecture 14 (Reductions): Section 8.1, 8.2.
• Lecture 15 (P and NP): Section 8.2,8.3.
• Lecture 16 (Mid-Term, NP-completeness): Section 8.4,8.5,8.6,8.7,8.8.
• Lecture 17 (co-NP, PSPACE): Section 9.1,9.2
• Lecture 18 (Fast Algorithms for Trees, Fixed Parameter Tractability): Section 10.1,10.2,10.3
• Lecture 19 (Tree Width): Section 10.4
• Lecture 20 (Approximation Algorithms: Greedy): Section 11.1,11.3
• Lecture 21 (Approximation Algorithms: Dynamic Programming, LP rounding): Section 11.8,11.6
• Lecture 22 (Approximation Algorithms: Semi-Definite Programming): Handout.
• Lecture 23 (Hardness of Approximation): See notes by Shuchi Chawla.
• Lecture 24 (Weighted Majority): Class Notes.
• Lecture 25 (Game Theory, 2-player Zero sum game, Linear Programming): Class Notes.