Princeton University logo
Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design
  Sanjeev Arora

  Fall 2008

Course Summary

Design and analysis of algorithms is an important part of computer science today. This course introduces students to advanced techniques for algorithm design and analysis, and explores a variety of applications.

We will devote about a couple of weeks each to several major areas of algorithms research: data structures, online algorithms, maximum-flow, linear programming, Markov Chain Monte Carlo (MCMC), algorithms in machine learning, internet algorithms and algorithms for large data sets.  Enroute, we will encounter various useful ideas, including randomization, probabilistic analysis, amortized analysis, competitive analysis, eigenvalues, high dimensional geometry, and random walks.

Prerequisite:  One undergraduate course in algorithms, or equivalent mathematical maturity. Listeners and auditors are welcome. There will be 5-6 homeworks during the term, and a take-home final exam. We may read a few research papers and have a few "field trips" (attending interesting talks on cutting edge algorithms research). There is no official text. Instead, we will use assorted online resources.

Administrative Information

Lectures: MW 1330-1450   Room 301, CS Bldg. First meeting: Sept 15

Professor: Sanjeev Arora- 307 CS Building - 258-3869 arora [AT] cs.princeton.edu
                  Office hours by appointment

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

Homeworks

HW 1
HW 2 was handed out in class; no printout.
HW 3.
HW4

Final exam: Finish by Jan 15 5pm; drop off in my office (307). You can use any course material but no other resources.

Lecture outlines and assigned readings

(Updated as the semester progresses.)

The course is broadly following the 2005 and 2006 offerings.


Lecture
 Assigned reading
 Optional reading and other links
1. Universal hashing. Probability and random variables.
 First  8.5 pages of Universal Hashing by  Peter Bro Miltersen.
2. Variations of hashing: perfect, k-wise, cryptographic. Some applications (eg fingerprinting, set estimation)
 Scribe notes by Sushant Sachdeva.


 		Additional notes on hashing (unedited): one, two
3. Introduction to competitive analysis, list update. A survey of self-organizing data structures, Albers and Westbrook (pages 1-17).
4. Loglog n -competitive update for
Binary Search Trees
 Scribe notes by Rong Ge
 Original Paper by Demaine, Harmon, Iacono, Patrascu,
5. Competitive BSTs contd; intro to k-server problem
 Scribe notes above.
6. Competitive analysis for harmonic k-server algorithm.
Paper by Bartal and Grove
7. No class; field trip to Alon's talk on Hashing, Coloring, Coding.

8. Dynamic programming, a simple idea that should be in your toolkit. Examples: Algorithm for TSP, Approximation Scheme for Euclidean TSP
 Survey paper by Arora; we only did the "First cut" algorithm for Euclidean TSP.
9. No class
10. Introduction to Linear Programming, Polytope theory, and Seidel's algorithm for solving LPs in constant number of dimensions.
First few sections of Michael Goldwasser's survey of randomized simplex algorithms
11. Introduction to solution of LPs: The Ellipsoid method Santosh Vempala's notes on the ellipsoid method. For a discussion of number of bits of precision needed, see Section 11 of Michel Goeman's notes on linear programming. Sections 6-7 in these notes have a description of the Simplex method which we briefly outlined in class.

 Michel Goeman's notes on linear programming.

Relevant xeroxed pages from Groetschel, Lovasz, Schrijver's book were handed out as well.
12. Using LPs to solve matchings, flows, and other problems.
 Sanjeev Arora's notes on LP duality.
13. LP duality. John von Neumann's minmax theorem.
Lecture notes by Avner Magen
14. Designing approximation algorithms using Linear programs
 Original article by Goemans and Williamson
15. Semidefinite programming (SDP) and designing Approximation Algorithms using it. Example: MAX-CUT David Williamson's lecture notes on SDP based approximation algorithms. Avner Magen's notes are very nice too.
16. SDP-based approximation algorithms, contd. Example: Chromatic Number.
 David Williamson's notes for the prev. lecture.
 Avner Magen's notes linked from the prev. lecture describe Wigderson's \sqrt{n} algorithm.
17. Eigenvalues,  and simple methods to compute eigenvalues. Convergence of random walks. Uses of singular vectors for clustering and web search.
 Sanjeev Arora's notes on eigenvalues and expansion. First 13 pages of Kleinberg's paper on web search.
18. Introduction to Machine Learning. The multiplicative weight update algorithm.
 Multiplicative weight update method: A survey by Arora, Hazan, Kale.
 What is machine learning by Rob Schapire.
19. More about MW update. Winnow, Combining experts, etc.
 Notes by Avrim Blum on applications of MW/Winnow.
20. Chernoff bounds and other concentration inequalities and their applications.
 Van Vu's Lecture notes on chernoff bounds.
 A marvelous survey of Concentration bounds by Colin McDiarmid.
21: Two algorithmic settings. Distributed algorithms (byzantine generals). Streaming algorithms.
 Scribe notes by Yuri Pritykin
The space complexity of approximating the frequency moments by Alon, Matias and Szegedy.
22. Approximation algorithms for counting problems. Dyers' DP-based algorithm for counting knapsack solutions.
 Scribe notes by Shi Li.
23. Arora-Rao-Vazirani algorithm for sparsest cut

24. ARV-contd


Resources and Readings

Further reading (books)

This course presents "greatest hits" of algorithms research and/or "must-know foundational ideas."  Usually the topics are covered in greater detail in specific textbooks.  Here are some great resources for additional reading:
  1. Randomized Algorithms by Motwani and Raghavan.
  2. Online computation and online analysis by Borodin and El-Yaniv.
  3. Probabilistic Method by Alon and Spencer.
  4. Approximation algorithms by Vijay Vazirani.
  5. Spectral graph theory by Fan Chung.