Princeton University CS Dept COS521: Advanced Algorithm Design Spring 2012

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] cs.princeton.edu
Nikhil Srivastava

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

Homeworks

HW 1. Due Fri Feb 24 by 5pm.
HW 2. Due Fri Mar 9 by 5pm.
HW 3. Due Fri Mar 30 by 5pm.
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 R^d.) 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 l₁ 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

Michel Goemans's lecture notes.
Lecture notes from CMU's grad algorithms course
The CMU website on ALGORITHMS IN THE REAL WORLD

Princeton University Computer Science Department

Computer Science 521 Advanced Algorithm Design