Princeton University
|
Computer Science 521
|
Spring 2013
|
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.
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
| 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. |
|