Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design
 Sanjeev Arora

  Fall 2005

Course Summary

Design and analysis of algorithms is an important part of computer science today. This course introduces students to advanced techniques for designing and analysing algorithms, and explores their use in a variety of application areas. Prerequisite:  One undergraduate course in algorithms, or equivalent mathematical maturity. Listeners and auditors are allowed. There will be 5-7 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). In lieu of an official text we will use assorted online resources.

We will start by surveying some simple but powerful ideas in data structures, and how they are useful in a variety of situations. Thereafter we will devote a couple of weeks each to a few active areas of algorithms research: online algorithms, max-flow, linear programming, Monte Carlo Markov Chain (MCMC) algorithms for enumeration and counting problems, algorithms in AI and machine learning, Internet algorithms, algorithms for large data sets.  Along the way we will encounter various useful ideas, including randomization, probabilistic analysis, amortized analysis, competitive analysis, eigenvalues, high dimensional geometry, and random walks.

Administrative Information

Lectures: MW 1330-1450     FIRST LECTURE MON SEPT 19          Room 102, CS Bldg.

Professor: Sanjeev Arora - 307 CS Building - 258-3869 arora@cs.princeton.edu

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

CLICK HERE TO JOIN THE MAILING LIST FOR THIS  CLASS.

Homeworks


Take home Final


Here are the instructions, which you can read any time. When you are ready to work on the final, download it here.
It is due on Friday Jan 13 at 4pm in my office, room 307. You have to finish it within 48 hours after first reading it. (Honor system.)

Resources and Readings


Lecture outlines and assigned readings


Lecture
 Assigned reading
 Optional reading and other links
1. Probability and random variables. Various guises of hashing and some applications. First  8.5 pages of Universal Hashing by  Peter Bro Miltersen.
2. Analysis of random hashing (and the related problem of "Randomized Load Balancing"). Balls and bins, and a few applications. Bloom Filters. Relevant pages on balls and bins from Kleinberg-Tardos.
Network applications of Bloom Filters by Broder and Mitzenmacher.
3. Introduction to amortized analysis. Self-organizing data structures. 2-competitive algorithm for linked lists (Move to Front heuristic) and its optimality.  Reading:  A survey of self-organizing data structures, Albers and Westbrook (only the section on linked lists).
 Rest of Albers-Westbrook paper.
4. Splay trees and their analysis.   Choose one of the following: Goeman's notes;  or notes by Blum and Sleator: notes1  and notes 2 Most important data structure of the last 20 years; see here. For an animation, see here.
5. On-line algorithms. Competitive analysis applied to other problems. k-server problem. Analysis of randomized paging algorithm.   Online Computation by Irani and Karlin. (Read up to Section 4.2, but only skim Sections 2.3, 3.3, and 4.2.1.)
 Skim through Sections 7, 8.
6. More on randomized algorithms. Transforming biased coins into fair coins and vice versa. Byzantine generals problem, and a randomized solution.  First four pages of the original paper by Lamport, Shostak, and Pease, and this note which I wrote.
7. Introduction to max flow min cut. Edmonds-Karp algorithm. (guest lecturer: Kevin Wayne) Slides from the lecture.
8. (lecturer: James Lee) More max-flow algorithms. Dinitz's blocking flow idea and its use in the Goldberg-Rao algorithm (the current champion). Notes by Kurt Mehlhorn.
9. Matchings. Reducing bipartite matching to network flow. Hall's theorem derived from Max Flow Min Cut. Matching in general graphs and augmenting paths.   Notes by Santosh Vempala.
10. Finding augmenting paths in general graphs. Blossoms. 
Vempala's notes (same as above).
11. Linear programming. LP duality and Farkas's lemma. Special cases: Max-Flow Min-Cut Thm and von Neumann minimax theorem.   Readings: My notes on LP duality.  Wikipedia entry on game theory and on  minimax theorem.  Wikipedia entries on Nash equilibrium, which we did not cover. Blum and Sleator's notes .
12. Introduction to solution of LPs: ellipsoid method.    Scribe notes by Siddhartha Brahma. Some details were skipped and can be found in  Vempala's notes.
13. (guest lecturer: Satyen Kale) Intro to algorithms in AI/Machine learning. Data representations and concept classes. Peceptron algorithm. Intro to Support Vector Machines (SVMs).   What is machine learning (by Rob Schapire) and Andrew Ng's lecture notes on the perceptron algorithm.
14. (guest lecturer: Satyen Kale) AI algorithms contd. Online learning. Weighted majority algorithm and connection to lagrangean relaxation and linear programming. The multiplicative weights method: a meta-algorithm and its applications (by Arora, Elad Hazan, and  Satyen Kale).
15. Probabilistic arguments, probabilistic method and probabilistic analysis of algorithms. G(n, p) model of random graphs. Linearity of expectation, chebyshev's inequality, and chernoff bounds.
 My notes from 2002. Current research in random graph models is surveyed in David Aldous's course.
16.Dynamic programming (= Advanced Divide-and-conquer.). 2^{2n} algorithm for TSP. PTAS for geometric TSP.  First 9 pages of Arora's survey article from Math Programming.
17. Approximation algorithms using Linear programming.
 Arora's  brief notes. We did not cover the primal-dual method; see Goemans-Williamson survey.
18. Approximation algorithms using Semidefinite programming. Arora's brief notes.
 Goemans survey.
ARV paper avail. from arora's webpage.
19, 20  Eigenvalues, how to compute them by the power method, and applications to clustering/web search. Google's pagerank algorithm and Kleinberg's hubs and authorities algorithm.
 Scribe notes coming soon.
First 13 pages of Kleinberg's paper.
 My old notes on eigenvalues.
21. Eigenvalues and conductance of random walks. Counting problems (= #P problems). Using random walks for enumeration and counting problems (sketchy intro)
 Lecture notes from 2002 on Markov Chains and their applications..

 Sections in the notes dealing with lowerbounding the eigenvalue gap (via the relationship to conductance). A  more thorough treatment appears in  Jerrum-Sinclair's survey on MCMC Algorithms.
22) Introduction to streaming algorithms and algorithms for large data sets. Moment estimation using one pass and small space. (Alon, Matias, Szegedy.) Connection to Johnson-Lindenstrauss dimension reduction.
 Scribe notes by Chee Wei Tan. First 8 pages of Alon et al.'s paper. My lecture notes on dimension reduction.

 Rest of Alon et al's paper.  Some surveys appear on Muthukrishnan's webpage.
23) Internet algorithms. Internet content distribution. Consistent hashing. Brief intro to error correcting codes.
 Lecture notes on consistent hashing by Blelloch and Maggs (CMU link). Scribe notes by
Original paper by Karger et al.
24) Algorithmic brain theory. Efforts to understand the brain at an algorithmic level.
Paper1 and Paper2 by LG Valiant.
 The Circuits of the mind.Written in 1994 and Valiant has changed the details of his theory since then. See his papers.


Further reading (books)


This course presents "greatest hits" of algorithms research and/or "must-know foundational ideas."  Usually the topic will have received a fairly thorough treatment in a textbook. We are blessed with several great books on algorithms!
Here are some.

  1. Randomized Algorithms by Motwani and Raghavan.
  2. Online computation and online analysis by Borodin and El-Yaniv.
  3. Distributed Algorithms by Nancy Lynch. (in case our brief coverage of Byzantine generals intrigued you)
  4. Data Structures and Network Algorithms by RE Tarjan. (Flows, matchings etc. Now showing its age;  there are other more recent books on  LP and flows.)
  5. Geometric Algorithms and combinatorial optimization by Groetschel, Lovasz, Schrijver (aka GLS).  (everything about Ellipsoid algorithm and many many extensions)
  6. Intro to Computational Learning Theory by Kearns and Vazirani.
  7. Probabilistic Method by Alon and Spencer. (Indispensable reference on probabilistic arguments in TCS and combinatorics).
  8. Approximation algorithms by Vijay Vazirani.
  9. Spectral graph theory by Fan Chung.