Princeton University
|
Computer Science 521
|
Fall 2015
|
(Important: In light of the new grad course requirements, this course changed in Fall 2013 to make it more accessible to CS grads who are not specializing in theoretical CS. )
Design and analysis of algorithms is an important part of computer science today. This course gives a broad yet deep exposure to algorithmic advances of the past few decades, and brings students up to a level where they can read and understand research papers in algorithms. The course is suitable for advanced undergrads and non-CS grads as well.
Thematically, the biggest difference from undergrad algorithms (such as COS 423) is extensive use of ideas such as randomness, approximation, high dimensional geometry, which are increasingly important in most applications. We will encounter notions such as algorithm design in face of uncertainty, approaches to handle big data, handling intractability, heuristic approaches, etc. We will develop all necessary mathematical tools.
Prerequisites: One undergraduate course in algorithms (eg COS 423), or equivalent mathematical maturity. Listeners and auditors are welcome with prior permission.
Coursework: Two lectures/week. For motivated students, a 1-hour discussion of advanced ideas each week at Small World Coffee on Friday afternoon. There will be 5 homeworks over the semester, which will include some simple programming-based exploration of the lecture ideas using Matlab or other packages. (Collaboration OK on homeworks.) Everybody must either do a take-home final in January, or do a term project (in groups of 2). There is no official text. Instead, we will use assorted online resources.
Instructor: Sanjeev Arora- 307 CS Building - 609-258-3869 arora AT the domain name cs.princeton.edu
Teaching assistant: Yuanzhi Li.
ENROLLED STUDENTS SHOULD ADD THEMSELVES TO THE DISCUSSION LIST AT
PIAZZA.COM
Office hrs: Sanjeev: Tues-Thurs 4:30-5:30.
Single file of all course notes, home works
and final from 2014.
(you can refer to this; updated lecture notes will be posted
below)
(Schedule is similar
to 2014 with small changes.)
| Date, Topic |
Main Readings |
Additional readings (optional) |
| Sept 17: Course Intro.
Hashing, Balls and Bins, Load Balancing, Power of 2 choices, Cuckoo hashing. |
Lec 1
notes. |
Power
of 2 choices: A survey by Mitzenmacher et al. Mitzenmacher's blog post explaining cuckoo hashing. |
| Sept 22: Karger's Randomized Algorithm
for Min-Cut, and Improvements to it by Karger and Stein. |
Lec 2 notes. |
|
| Sept 24: Deviation bounds on random
variables: Markov, Chebyshev, and Chernoff. Applications to
balls and bins, and sampling/polling. |
Lec 3 notes. |
Colin
McDiarmid's excellent survey of concentration bounds.
See also Terry Tao's notes on Concentration of Measure. |
| Sept 29: (Guest lecture by Andrej
Risteski) Hashing to real numbers and applications to
counting # of distinct elements, and document similarity. |
Lec 4 notes. |
Hashing
for Similarity Search: A Survey by Wang, Shen,
Song, Ji |
| Oct 1: Linear thinking (LP, linear
models, notion of polynomial time.) |
Lec 5 notes. |
Linear
Programming .Fascinating historical article by G. B.
Dantzig, a key figure. Many of the events happened at
Princeton. |
| Oct 6: Approximation algorithms via
Linear Programming. |
Lec 6 notes. |
Design
of Approximation Algorithms by Williamson and Shmoys.
(Online book). |
| Oct 8: (Guest lecturer: Mark
Braverman): Stable matchings, stable marriages, and price of
anarchy. |
Lecture notes coming soon.(In the meantime
use last year's notes.) |
|
| Oct 13: Decision making under
uncertainty, and some life lessons. Rational
choice theory, optimum decision making via dynamic
programming, Markov decision processes (and how to find
stationary solutions via LP). |
Lec 8 notes. A tutorial introduction to decision theory by D. W. North. |
Wikipedia
page. For further info on MDPs, see Andrew Moore's lecture notes and Jay Taylor's lecture notes. |
| Oct 15: Decision making under total
uncertainty: Multiplicative Weights Update algorithm. |
Lec 9 notes. |
Arora,
Hazan, Kale survey. |
| Oct 20: Using multiplicative weights to
solve LPs and manage portfolios. (+ glimpses of duality). |
Lec 10 notes. |
|
| Oct 22: (Guest lecturer: Elad Hazan)
Going with slope: offline, online, and randomly. (Various
flavors of gradient descent.) |
Lec 11 notes.
(Thanks to Ariel Schwartzmann Cohenca for updating last
year's notes.) |
The
Zen of Gradient Descent (blog post by Moritz Hardt) |
| Oct 27: High-dimensional geometry, Curse
of Dimensionality, and Dimension Reduction. |
Lec 12 notes. |
Jelani Nelson's lecture
notes on Dimension Reduction. (Also has discussion of
faster versions.) He prefers these newer and more extensive notes. |
| Oct 29: Random walks, Markov
Chains, and how to analyse them. Also, Markovian
Models. |
Lec 13 notes. |
Chapter in Hopcroft-Kannan. Online text by Aldous and Fill is a great resource on random walks, including discussion of other parameters associated with a random walk, and techniques for computing them. |
| Nov 10: Intrinsic dimensionality of data
and low-rank matrix approximations (SVD). |
Lec 14 notes. |
Paper on Latent
Semantic Analysis |
| Nov 12: SVD, Power Method, and Recovering
Stochastic Block Models. (+ glimpses of eigenvalues of random matrices) |
Lec 15 notes. |
Topics
in Random matrix theory by T. Tao. For more coverage see Introduction to Random Matrices (by Anderson, Guionnet, and Zeitouni). |
| Nov 17: Semidefinite Programming (SDP)
and Approximation Algorithms. |
Lec 16 notes. |
Robert
Freund's lecture notes on SDP. Applications of SDP by Vendenberghe and Boyd. Limits on Approximation Algorithms: PCPs and Unique Games. (Dimacs Lecture Notes) |
| Nov 19: Oracles, Ellipsoid Method, and
their uses in Convex Optimization. |
Lec 17 notes. Santosh Vempala's notes have more detailed analysis. |
Amusing NY
Times article on discovery of Ellipsoid Method. (copyright
NY Times) |
| Nov 24: LP Duality and Minmax Theorem. |
Lec 18 notes. |
|
| Dec 1: Equilibria and Algorithms. (Nash Equilibria, Price of Anarchy, and Correlated Equilibria.) |
Lec 19 notes. |
|
| Dec 3: Protecting information against
loss: Intro to Coding Theory. |
Lec 20 notes. |
Modern
Coding Theory by Richardson and Urbanke. |
| Dec 8: Taste of Cryptography: Secret
Sharing and Multiparty Computation. |
Lec 21 notes. |
Principles
of Modern Cryptography by Dan Boneh. |
| Dec 10: Counting and Sampling Problems. |
Lec 22 notes |
Eric
Vigoda's lecture notes on this topic from 2006. |
| Dec 15: Part 1: Real-life environments
for big-data computations (MapReduce etc.) Part 2:
Advanced approximation algorithms via SDPs. (O(log n)
approximation for Balanced Separator.) |
Lec 23 notes. Rough notes on SDP-based approximation |
Arora,
Rao, Vazirani paper on Sparsest Cut. |
| Dec 17: Heuristics: Algorithms we don't
yet know how to analyse. |
Lec 24 notes. |
Description/guidelines to term
project
(for students who come to the Friday meetings)
