Princeton University

Computer Science 521

Fall 2005 
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 57 homeworks during the term, and a takehome 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, maxflow, 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.
Professor: Sanjeev Arora  307 CS Building  2583869 arora@cs.princeton.edu
Graduate Coordinator: Melissa Lawson
 310 CS Building  2585387 mml@cs.princeton.edu
CLICK
HERE TO JOIN THE MAILING LIST FOR THIS CLASS.
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 KleinbergTardos. Network applications of Bloom Filters by Broder and Mitzenmacher. 

3. Introduction to amortized analysis. Selforganizing data structures. 2competitive algorithm for linked lists (Move to Front heuristic) and its optimality.  Reading: A
survey of selforganizing data structures, Albers and Westbrook
(only the section on linked lists). 
Rest of AlbersWestbrook 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. Online algorithms. Competitive analysis applied to other problems. kserver 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. EdmondsKarp algorithm. (guest lecturer: Kevin Wayne)  Slides from the lecture.  
8. (lecturer: James Lee) More maxflow algorithms. Dinitz's blocking flow idea and its use in the GoldbergRao 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: MaxFlow MinCut 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 metaalgorithm 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 Divideandconquer.). 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 primaldual
method; see GoemansWilliamson
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 JerrumSinclair'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
JohnsonLindenstrauss 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. 