Princeton University

Computer Science 521

Fall 2008 
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, maximumflow, 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 56 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). There is no official text. Instead, we will use assorted online resources.
Professor: Sanjeev Arora 307
CS Building  2583869 arora
[AT] cs.princeton.edu
Office hours by appointment
Graduate Coordinator: Melissa Lawson
 310 CS Building  2585387 mml [AT] cs.princeton.edu
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, kwise, 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 selforganizing data structures, Albers and Westbrook (pages 117).  
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 kserver problem 
Scribe notes above. 

6. Competitive analysis for
harmonic kserver 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 67 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: MAXCUT  David Williamson's lecture notes on SDP based approximation algorithms.  Avner
Magen's notes are very nice too. 

16. SDPbased 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 


22. Approximation algorithms for
counting problems. Dyers' DPbased algorithm for counting knapsack
solutions. 
Scribe notes by Shi Li. 


23. AroraRaoVazirani algorithm
for sparsest cut 


24. ARVcontd 
