Princeton University CS Dept COS521: Advanced Algorithm Design Spring 2013

Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design

Moses Charikar

Spring 2013

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 4-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: Mon-Wed 1:30-2:50 Room 402, CS Bldg. First meeting: Feb 4.

Instructor: Moses Charikar: 305 CS Building - 258-7477 moses [AT] cs.princeton.edu

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

Homeworks

Homework 1 (due Wed, March 6)
Homework 2 (due Sun, April 7)
Homework 3 (due Thu, April 25)

Lecture outlines and assigned readings

(Updated as the semester progresses.)

The course is broadly following the the Spring 2012 offering.

Lecture topic	Assigned Readings	Additional readings
1) Feb 4: Hashing and Load Balancing 1. Random hash functions. Universal hashing. Perfect hashing. Balls & bins	First 6 pages of Miltersen's survey on hashing. Scribe notes by Linpeng Tang (unedited).	Scribe notes from 2008 by Sushant Sachdeva.
2) Feb 6: Hashing and Load Balancing 2. Power of 2 choices. Cuckoo Hashing	Scribe notes by Sachin Ravi (unedited).	Satish Rao's notes on the power of two choices. Anupam Gupta's notes on the power of two choices.
3) Feb 11: Hashing and Applications to Compact Data Representation. Analysis of Cuckoo hashing. Minwise hashing for set similarity. Bloom Filters.	Scribe notes by John McSpedon (unedited).	Cuckoo Hashing paper by Pagh and Rodler. Network applications of Bloom filters by Broder and Mitzenmacher. (didn't cover this in class) Ryan O'Donnel's notes on Chernoff bounds.
4) Feb 13: Streaming Algorithms. Guest lecture by Jelani Nelson	Scribe notes by Michael Zhu (unedited).	Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan: Counting Distinct Elements in a Data Stream. RANDOM 2002: 1-10 (Algorithm 1 in their paper, for distinct elements) Amit Chakrabarti's notes (sections 1, 4, and 6 for AMS and heavy hitters) Piotr Indyk's notes (section 2 for proof that randomness and approximation are both necessary for, say, distinct elements)
5) Feb 18: Online Algorithms. List update, Caching.	Scribe notes by Kevin Lin (unedited).
6) Feb 20: Online Algorithms contd. Caching (randomized algorithm), lower bounds, learning from experts.	Scribe notes by Borislav Hristov (unedited).
7) Feb 25: Multiplicative Weights and Zero Sum Games learning from experts contd., multiplicative weights update, zero sum games, minimax theorem	My notes on learning from experts. My notes on zero sum games and minimax theorem.	Survey on the multiplicative weights method and its applications by Arora, Hazan, Kale.
8) Feb 27: Zero sum games contd. Approximately optimal strategies for zero sum games via multiplicative weights, intro to linear programming, proof of minimax theorem.	See notes for previous lecture (still missing application of multiplicative weights to zero sum games.
9) Mar 4: LP duality	Anupam Gupta's notes on LP duality.	Michel Goeman's notes on linear programming.
10) Mar 6: LP duality contd. Max-flow min-cut via LP duality, approximation algorithms via LP.
11) Mar 11: LP based approximation algorithms	David Williamson's notes on various ways to design approximation algorithms for set cover via LP.
12) Mar 13: Ellipsoid method.	Ryan O'Donnell's notes on the Ellipsoid Algorithm	Ryan O'Donnell's notes on Grotschel-Lovasz-Schrijver
13) Mar 25: Introduction to Semidefinite Programming (SDP). Max Cut	Scribe notes by Aaron Schild (unedited).
14) Mar 27: SDP contd. Arora-Rao-Vazirani relaxation for sparsest cut.	Arora-Rao-Vazirani paper on sparsest cut. Read definitions in Section 2, Corollary 2 (with proof), algorithm in Section 3, and simple O(log n) analysis outlined in beginning of Section 3.1.
15) Apr 1: Spectral partitioning. Cheeger's inequality	Luca Trevisan's course notes: Linear algebra preliminaries Cheeger's inequality: easy direction .
16) Apr 3: Spectral partitioning contd. power method to find eigenvalues/eigenvectors	Luca Trevisan's course notes: Cheeger's inequality: difficult direction . Power method for eigenvalues/eigenvectors.
17) Apr 8: Dimension Reduction. (guest lecture by Huy Nguyen) Johnson Lindenstrauss Lemma on dimension reduction in Euclidean space.	Simple proof of the JL Lemma by Dasgupta and Gupta. Jiri Matousek's notes on connection to compressed sensing (a hot topic of current research in Math/Statistics/CS).
18) Apr 10: Introduction to Compressed Sensing.	See Matousek's notes above. Slides by Piotr Indyk and Martin Strauss on proof that RIP implies correctness of Basis Pursuit (decoding via LP).	Survey talks on recent directions in compressed sensing/sparse recovery at April 12 Intractability Center meeting .
19) Apr 15: Sparsest Cut LP. connection to metric embeddings	Luca Trevisan's notes .
20) Apr 17: Bourgain's theorem. embedding arbitrary metrics into normed spaces	Luca Trevisan's notes . Scribe notes by Tengyu Ma (unedited).
21) Apr 22: Distance Approximation by Trees. O(log^2 n) approximation by recursive partitioning	Lecture notes by the late Avner Magen.
22) Apr 24: Distance/Capacity Approximation by Trees O(log n) approximation by FRT, introduction to capacity approximation.	Analysis of FRT in Avner Magen's notes above. Raecke's paper on capacity approximation via distribution on trees. Scribe notes by Ohad Fried (unedited).
23) Apr 29: Capacity Approximation by Trees Reduction to distance approximation by Racke.	Raecke's paper above. We covered material in Section 1.2, Section 2 (before 2.1). Section 2.1 gives an (multiplicative weights style) algorithm to find a distribution on trees; I gave an existence proof based on duality instead. Section 3 describes several applications, including min-bisection and oblivious routing.
24) May 1: Efficient solver for Symmetric Diagonally Dominant (SDD) Systems.	We discussed this paper by Kelner, Orecchia, Sidford and Zhu. Covered material from Sections 1,2,3,4,6 (proofs omitted from analysis in Sections 4 and 6, also omitted discussion of cycle update data structure).

Resources and Readings

Notes on Mathematics for Computer Science by Lehman, Leighton and Meyer (good reference for mathematical background).
Michel Goemans's lecture notes.
Lecture notes from UC Berkeley's Combinatorial Algorithms and Data Structures course
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