Princeton University Computer Science Department

Computer Science 521 Advanced Algorithm Design Moses Charikar

Spring 2011

Course Summary

Administrative Information

Lectures: MW 1330-1450, Room: 301

Professor: Moses Charikar - 305 CS Building - 258-7477 moses@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Final

• The final is due 48 hours after you start, latest by May 18.
  When you are ready to work on the final, you can download it here:
  ( pdf , latex available by request)

Homework

• Homework 1 (in class).
  
  
• Homework 2 ( pdf , tex ) Due: Wed, April 6.
  
  
• Homework 3 [practice problems] ( pdf , tex )

Schedule and Readings

• Jan 31 - Mar 16: Approximation Algorithms
  Reading: The Design of Approximation Algorithms by Williamson and Shmoys.
  (Chapters 1, 2 [2.3,2.4,2.6], 3 [3.1,3.2], 4 [4.1,4.2,4.3], 6 [6.1,6.2,6.5], 7 [7.4,7.6,7.7], 8 [8.3,8.4])
  
  
• Mar 21, 23: The Multiplicative Weight Update Method
  Reading: Survey on the Multiplicative Weights Update Method by Arora, Hazan, Kale.
  (Sections 1.1, 2, 3.1, 3.2, 3.3)
  
  
• Mar 28 : Online Primal-Dual
  Reading: Survey on online primal-dual algorithms by Buchbinder and Naor.
  (Sections 3, 4.1, 4.2 [Algorithm 1], 4.4)
  See also these slides by Seffi Naor.
  
  
• Mar 30 : Online Set-Cover and Weighted Paging
  Reading: Section 5 of online primal-dual survey above.
  A Simple Proof for Weighted Caching by Bansal, Buchbinder and Naor.
  
  
• Apr 4, 6: Online Matching
  Reading: Online Bipartite Matching Made Simple by Birnbaum and Mathieu.
  Further Reading: Adwords and Generalized Online Matching by Mehta, Saberi, Vazirani and Vazirani.
  In addition to this, there have been several recent papers on online stochastic matching that beat 1-1/e under the assumption that the vertices that appear online come from a distribution (instead of being adversarially chosen), or that they are a permutation of some fixed unknown graph.
  
  
• Apr 11: Chernoff Bounds, Balls in Bins, Power of 2 choices
  Reading: See these notes by Anupam Gupta.
  
  
• Apr 13: Randomized MinCut
  Reading: An O~(n^2) Algorithm for Minimum Cuts by Karger and Stein.
  
  
• Apr 18: Dimension Reduction: Johnson-Lindenstrauss Lemma
  Reading: Lecture notes by Michel Goemans and Ben Rossman (see the second proof of Johnson-Lindenstrauss in these notes).
  The proof in these notes was given by Gupta and Dasgupta here .
  
  
• Apr 20: Streaming Algorithms: Frequency Moments, Distinct Elements
  Reading: My notes on streaming algorithms and estimating distinct elements.
  See these notes by Avrim Blum and Anupam Gupta on the Alon-Matias-Szegedy streaming algorithm for estimating the second frequency moment.
  
  
• Apr 25: Eigenvalues and Expansion
  Reading: Sanjeev Arora's notes on eigenvalues and expansion.
  
  
• Apr 27: Sparsest Cut, Bourgain's theorem
  Reading: Section 15.1 in Williamson-Shmoys. Refer to these notes by Harald Racke for the proof of Bourgain's theorem and the matching lower bound.
  
  
• May 2: Bourgain's theorem wrapup, overview of Metric Embeddings in Approximation
  Reading: