Computer Science 521
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.
Instructors: Sanjeev Arora- 307
Building - 258-3869 arora [AT] cs.princeton.edu
Graduate Coordinator: Melissa Lawson -
310 CS Building - 258-5387 mml [AT] cs.princeton.edu
|1) Feb 7: Hash for breakfast, lunch and
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.
notes from 2004.
|2) Feb 9: Hashing applications.
notes by Shilpa Nadimpalli.
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
|4) Competitive analysis for caching algorithms.
Intro to k-server
||pages 1-5 and section 4.1 of
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.
|9) Dynamic Programming: A simple but important
tool. Application: (1+\eps)-approximation to Euclidean TSP
paper by Arora. (We only did the simple structure
||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.
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
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
(just section 1.1)
|Dan Spielman's notes on the non-regular case|
|13) Designing approximation algorithms
via Linear Programming.
Johnson's column on limits of approximation.
The Shmoys-Williamson book on Approximation Algorithms is electronically downloadable.
|14) Designing approximation
algorithms via Semidefinite
|15) Finish log(n) approx for
Spectral Partitioning and Cheeger's Inequality.
| Luca Trevisan's notes, I
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
Probabilistic Approximately Correct (PAC) learning. Learning a halfspace, and a rectangle.
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.
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
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.)
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.)
notes by the late Avner Magen.
Scribe notes forthcoming.
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|