Princeton University logo
Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design
  Moses Charikar

  Fall 2006

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.

Professor: Moses Charikar - 305 CS Building - 258-7447 moses [AT] cs.princeton.edu
                  Office hours by appointment

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

CLICK HERE TO JOIN THE MAILING LIST FOR THIS  CLASS.

Take-Home Final

The take home final will be posted here on Jan 17. You must finish the final 48 hours after first reading it. The last day to submit your solutions is Mon, Jan 22. You can use any notes/handouts from the class and can quote any results from there. You are not allowed to use any other sources.

To get an idea of what the final might be like, take a look at last year's final .

This is the final exam (ps,pdf). Do not read it before you are ready to work on it. Send Moses email to let him know you have started the test in case any clarifications need to be made.

All the best !

Homeworks


Lecture outlines and assigned readings


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. Perfect hashing.  Bloom Filters. Additional notes on hashing (unedited): one, two
Network applications of Bloom Filters by Broder and Mitzenmacher.
3. Balls and bins, and a few applications. Chernoff bounds, martingales, Azuma-Hoeffding inequality.


4. Introduction to competitive analysis, list update.
 A survey of self-organizing data structures, Albers and Westbrook (pages 1-17).
5. Online algorithms contd: caching - deterministic and randomized algorithms.
 Lecture notes (from Berkeley): deterministic algorithms (Section 2), and randomized algorithms.

6. Online load balancing - uniform machines, restricted machines and related machines.
 "Online Computation and Competitive Analysis", Borodin and El Yaniv, Chapter 12, Sections12.1-12.3. Note: the proof in the restricted machines case is not quite correct. See the original proof in the paper of Azar, Naor and Rom (Section 3.1).
7. Introduction to max flow.
 Lecture slides (courtesy Kevin Wayne).
8. Max flow contd - Goldberg-Rao.
 Notes by Kurt Mehlhorn.
9. Matchings in bipartite graphs, Hall's theorem, augmenting paths
 Notes by Santosh Vempala.
10. Matchings in general graphs, blossoms.
 see above
11. Introduction to Linear Programming and duality.
 Sanjeev Arora's notes on LP duality. Michel Goeman's notes on linear programming.
12. (guest lecturer: Satyen Kale) Intro to algorithms in Machine learning. Peceptron algorithm. Introduction to Support Vector Machines (SVMs).
What is machine learning by Rob Schapire. Andrew Ng's lecture notes on the perceptron algorithm.
13. (guest lecturer: Satyen Kale) AI algorithms contd. The multiplicative updates method and connection to lagrangean relaxation and linear programming.
The multiplicative weights method: a meta-algorithm and its applications by Sanjeev Arora, Elad Hazan, and Satyen Kale.
14. 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.
 I mentioned the paper of Spielman and Teng that introduced smoothed analysis as a method for analyzing the practical behavior of algorithms, inspired by trying to understand why Simplex works well in practice. Read Section 1 for an overview of work in this area.
15. Approximation Algorithms using Linear Programs
 David Williamson's lecture notes on various ways to design approximation algorithms for set cover. Satish Rao's lecture notes on minimum congestion routing via LP.
This paper showed that the ln n guarantee for set cover is almost optimal. A recent paper shows that the Raghavan-Thompson randomized rounding procedure for minimum congestion is essentially optimal.
16. Approximation Algorithms based on Linear Programs (contd.)
 See David Williamson's notes above.
17. Approximation Algorithms based on Semidefinite Programs
 David Williamson's lecture notes on SDP based approximation algorithms.
The second Karger-Motwani-Sudan rounding procedure for graph coloring described in Williamson's notes is slightly different from the one I showed in class. See page 11 of the paper by Karger Motwani Sudan for a description of this.
18. Eigenvalues and expansion
 Sanjeev Arora's notes on eigenvalues and expansion.
19. Eigenvalues and expansion (contd)

20. Randomized Algorithms: Min Cut
Notes on randomized min-cut from CMU.
21. Randomized Algorithms: Identity testing
Motwani and Raghavan, Chapter 7, pages 161-172
22. Parallel and Distributed Algorithms. Brief introduction: Byzantine agreement and Parallel Maximal Independent Set.
Notes on parallel maximal independent set from Georgia Tech. Motwani and Raghavan, pages 358-361.
23. Algorithms for Large Datasets: Streaming Algorithms
 The space complexity of approximating the frequency moments by Alon, Matias and Szegedy.
24. Algorithms for Large Datasets: Nearest Neighbor Search


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.