Date  Contents  References  Remarks  Scribe notes  
Network Flows  
Lecture 1  Wed Aug 26  Introduction, the maxflow mincut theorem  CLRS: Chapter 26 KT: Chapter 7 GoldbergRao paper 
HW 1 out  Notes 
Lecture 2  Fri Aug 28  Augmenting paths, blocking flows  Notes  
Lecture 3  Wed Sep 2  Scaling: The GoldbergRao algorithm  Notes  
Lecture 4  Fri Sep 4  Preflows and pushrelabel algorithms  Notes  
Lecture 5  Wed Sep 9  Minimum cost flows: cycle calcellation, cost scaling  HW 2 out  Notes  
Linear programming  
Lecture 6  Fri Sep 11  Introduction and examples, weak duality  CLRS: Chapter 29 DPV: Chapter 7 KT: Chapter 11.6 V: Chapter 12 WS: Chapter 1.2, 4.3 
HW 1 due  Notes 
Lecture 7  Wed Sep 16  Strong duality, complementary slackness, applications  Same as 6  
Lecture 8  Wed Sep 16  LP solvers (basics): simplex, ellipsoid and separation oracles, interior point methods  Notes  
Fri Sep 18  Dept meeting: Lecture rescheduled to Sep 16  
Lecture 9  Wed Sep 23  Separation oracles  Same as 8  
Randomized Algorithms  
Probabilistic tools: Linearity of expectation, coupon collector, balls in bins 
MR: Chapter 3, 4 MR: Chapter 11.1, 11.2 MR: Chapter 1, 10.2 
HW 2 due HW 3 out 
Notes  
Lecture 10  Fri Sep 25  Probabilistic tools: Tail bounds (Markov, Chebyshev, Chernoff)  Same as 9  
Lecture 11  Wed Sep 30  Monte Carlo sampling, DNF counting  Notes  
Lecture 12  Fri Oct 2  Monte Carlo algorithms: randomized contraction for global mincut
Las Vegas algorithms: randomized quicksort 
Notes  
Wed Oct 7  Midterm 1  
NPhardness and Approximation Algorithms 

Lecture 13  Fri Oct 9  The complexity classes P and NP
NPhardness and NPcompleteness: Polynomialtime reductions Introduction to approximation algorithms: vertex cover 
CLRS: Chapter 34, 35 KT: Chapter 8, 11.3, 11.4 V: Appendix A, Chapter 1, 2 WS: Appendix B, Chapter 1.6 
Notes  
Lecture 14  Wed Oct 14  Greedy approximation: set cover, bipartite matching Dual fitting: vertex cover 
V: Chapter 13 WS: Chapter 1.6, 9.4 
HW 4 out  Notes 
Fri Oct 16  Instructor travel: Lectures on Oct 23 and Oct 28 extended  HW 3 due  
Lecture 15  Wed Oct 21  Dual fitting: set cover, bipartite matching LP rounding: vertex cover (threshold rounding), set cover (randomized rounding) 
KT: Chapter 11.6 V: Chapter 14, 16, 17 WS: Chapter 1.7, 5, 11.1 
Same as 14 Notes 

Lecture 16  Fri Oct 23  LP rounding: bipartite matching (iterative rounding) Steiner tree and TSP: MST, Christofides 
Notes  
Lecture 17  Fri Oct 23 Wed Oct 28 
Primaldual methods: MST algorithms, Steiner forest (AKR/GW)  V: Chapter 22, 24 WS: Chapter 1.5, 7.3, 7.4, 7.6 GoemansWilliamson paper 
Notes  
Lecture 18  Wed Oct 28  Strong and Weak NPhardness
Polynomialtime Approximation Schemes 
MR: Chapter 11 V: Chapter 8 WS: Appendix B, Chapters 1.1, 3 
Notes  
Lecture 19  Fri Oct 30  Semidefinite programming  V: Chapter 26 WS: Chapter 6 
HW 4 due  Notes 
Lecture 20  Wed Nov 4  Integrality gaps: vertex cover, minimum spanning tree  Notes  
Other Topics  
Lecture 20  Wed Nov 4  Online Algorithms: Rentorbuy problems  BE: Chapter 3, 4 MR: Chapter 13 
Notes  
Lecture 21  Fri Nov 6  Online Algorithms: Paging and kserver  BE: Chapter 12  HW 5 out  Same as 20 
Lecture 22  Wed Nov 11  Data Streaming Dimensionality reduction 
Notes  
Lecture 23  Fri Nov 13  Lower bounds: informationtheoretic and computational  Same as 22  
Lecture 24  Wed Nov 18  Beyond worstcase analysis  HW 5 due  
Fri Nov 20  Midterm 2 