Princeton University

Computer Science 521

Spring 2012

Design and analysis of algorithms is an important part of computer science today. This course gives a broad yet deep exposure to algorithms research of the past few decades, and brings students up to a level where they can subsequently follow papers in any subarea of algorithms. The course is suitable for advanced undergrads and grads (including those who don't intend to specialize in theoretical CS),
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, high dimensional geometry, 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 with prior permission. There will be 5 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.
Instructors: Sanjeev Arora 307
CS
Building  2583869 arora [AT] cs.princeton.edu
Nikhil Srivastava
Graduate Coordinator: Melissa Lawson 
310 CS Building  2585387 mml [AT] cs.princeton.edu
Lecture topic 
Assigned Readings 
Additional readings 
1) Feb 7: Hash for breakfast, lunch and
dinner. Various types of hashings. Random hash functions. Balls & bins, Large Deviation Bounds 
First 8.5 pages of Miltersen's
survey on hashing. Scribe notes from 2008 by Sushant Sachdeva. 
Scribe
notes from 2004. 
2) Feb 9: Hashing applications.
Consistent hashing. 
Scribe
notes by Shilpa Nadimpalli. 
Network
applications of Bloom filters by Broder and
Mitzenmacher. (We didn't get to this topic in class.)
Lecture notes on consistent hashing by Blelloch and Maggs. Original paper on consistent hashing (from Akamai website) 
3) Competitive Analysis and Online Algorithms. 
pages 15 of the survey
of selforganizing data structures by Albers and
Westbrook. 

4) Competitive analysis for caching algorithms.
Intro to kserver
problem. 
pages 15 and section 4.1 of
the survey
by Irani and Karlin 
A nice survey of online algorithms circa 2004 by Susanne Albers. (Few proofs though.) 
5) Intro to linear programming  
6) Soft heaps (guest lecture by Bob Tarjan)  paper by Kaplan and Zwick  
7) The Ellipsoid Algorithm  Ryan O'Donnell's lecture notes  The
Ellipsoid Method and its Consequences in Combinatorial
Optimization, Grotschel, Lovasz, Schrijver '80 Ryan's notes on GLS 
8) Linear programming duality, complementary
slackness, application to max flow / min cut. 
Anupam
Gupta's notes 

9) Dynamic Programming: A simple but important
tool. Application: (1+\eps)approximation to Euclidean TSP 
Survey
paper by Arora. (We only did the simple structure
theorem.) 
A recent AMS article
on the topic. (Link may expire or change in a month) 
10) Dynamic programming
contd: Dyer's FPRAS for counting
the number of solutions to a Knapsack problem. Side detours: Counting problems, Monte Carlo, Chernoff Bounds. 
Eric Vigoda's lecture
notes on Dyer's algorithm. 
Survey
of Concentration Bounds (Chernofftype) by Chung and
Lu we only need Theorem 3.1 and 3.2. For interested students: a more general version of Dyer's result due to Gopalan et al. 
11) JohnsonLindenstrauss dimension reduction, highdimensional Gaussians  Nick Harvey's notes  Berkeley
notes Sasha Barvinok's notes on measure concentration Keith Ball's notes on high dimensional geometry 
12) Random walks, eigenvalues of graphs, the power method, MCMC and conductance (briefly)  Berkeley notes I
and II
(just section 1.1) Sanjeev's notes 
Dan Spielman's notes on the nonregular case 
13) Designing approximation algorithms
via Linear Programming. Randomized rounding. 
Sanjeev's notes. 
David
Johnson's column on limits of approximation. The ShmoysWilliamson book on Approximation Algorithms is electronically downloadable. 
14) Designing approximation
algorithms via Semidefinite
Programming. 
Sanjeev's
notes. 

15) Finish log(n) approx for
Balanced Separator. Spectral Partitioning and Cheeger's Inequality. 
Luca Trevisan's notes, I
and II 
Dan
Spielman's notes on the nonregular case. Generalization to k eigenvalues Oveis Gharan, Lee, Trevisan 
16) Iterative methods for solving linear equations.  Dan Spielman' Notes  Koutis Miller
Peng Nearly Linear time solver Dan Spielman's ICM slides 
17) Introduction to Machine Learning. Concept
Class. Probabilistic Approximately Correct (PAC) learning. Learning a halfspace, and a rectangle. 
What
is Machine Learning? (lecture notes by Rob Schapire).

The general treatment of how
many samples are needed to learn a concept class involves VC
dimension. See these
lecture notes by Sanjeev. 
18) Multiplicative weight update
method, a useful technique in machine learning,
convex programming, decision theory, etc. 
Survey
by Arora, Hazan, Kale. 

19) Learning under the
uniform distribution, Fourier analysis of Boolean functions

Ryan O'Donnell's notes  A
survey of Boolean Fourier analysis, also by Ryan 
20) Error correcting codes,
Shannon's theorems, ReedSolomon codes 
Dan
Spielman's notes Venkat Guruswami's notes on decoding Madhu Sudan's notes on Shannon 

21) Metric spaces. Nearest neighbor
searching. Curse of dimensionality. Algorithms for
metric spaces of bounded doubling dimension. (Generalizes R^{d}.)
Epsilon nets 
Original
paper by Krauthgamer and Lee (we only did the
3approximation). Scribe notes forthcoming. 

22) Converting one metric
space into another (metric
embeddings and distortion). Embedding tree metrics
into l_{1} isometrically. Embedding every metric
probabilistically into tree metrics with distortion O(log
n). (In class we did log n log Delta.) 
Lecture
notes by the late Avner Magen. Scribe notes forthcoming. 
A
nice bibliography on metric embeddings (circa 2006)
compiled by Tim Roughgarden. Original papers by Bartal and FRT. 
23) Streaming Algorithms. Distinct elements, frequency moment estimation.  Berkeley Notes 