Princeton University logo
Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design

Sanjeev Arora

Nikhil Srivastava

  Spring 2012

Course Summary

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, maximum-flow, 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 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: Tues-Thurs 15:00-16:20   Room 402, CS Bldg. First meeting: Feb 7.

Instructors: Sanjeev Arora- 307 CS Building - 258-3869 arora [AT]
        Nikhil Srivastava              

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml [AT]


  1. HW 1. Due Fri Feb 24 by 5pm.
  2. HW 2. Due Fri Mar 9 by 5pm.
  3. HW 3. Due Fri Mar 30 by 5pm.
  4. HW 4. Due Tue May 1 by 5pm.

Lecture outlines and assigned readings

(Updated as the semester progresses.)

The course is broadly following the 2005 , 2006, and 2008 offerings.

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 1-5 of the survey of self-organizing data structures by Albers and Westbrook.

4) Competitive analysis for caching algorithms. Intro to k-server problem.
pages 1-5 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 (Chernoff-type)  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) Johnson-Lindenstrauss dimension reduction, high-dimensional 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 non-regular case
13) Designing approximation algorithms via Linear Programming.
Randomized rounding.
Sanjeev's notes.
David Johnson's column on limits of approximation.
The Shmoys-Williamson 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 non-regular 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, Reed-Solomon 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 Rd.) Epsilon nets
Original paper by Krauthgamer and Lee (we only did the 3-approximation). Scribe notes forthcoming.

22) Converting one metric space into another (metric embeddings and distortion). Embedding tree metrics into l1 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

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.