Princeton University
|
Computer Science 521
|
Fall 2016
|
(Important: In light of the new grad course requirements, this course changed in Fall 2013 to make it more accessible to CS grads and Masters Students 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 Thurs afternoon.) 5 homeworks, including 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 our own lecture notes and assorted online resources.
The course will be broadly similar to last year's offering.
Instructor: Sanjeev Arora (307
CS
Building - 609-258-3869 arora AT the domain name cs.princeton.edu)
Pravesh Kothari (219, CS
Building, 609-258-8014, Email: kothari AT cs
Teaching assistant: Fermi Ma ( fermim @ princeton . edu )
ENROLLED STUDENTS SHOULD ADD THEMSELVES TO THE DISCUSSION LIST AT
PIAZZA.COM
Office hrs: Sanjeev: Tues-Thurs 15:00-16:00.
Pravesh: Tues-Thurs 15:00-16:00
| Lecture Number/Date |
Required Reading |
Optional Reading |
| 1)Sept 15: Course intro. Hashing, Analysis tools. 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. |
| 2) Sept 20: Karger's Randomized Algorithm for Min-Cut, and Improvements to it by Karger and Stein. | Lec 2 notes. |
|
| 3) Sept 22: 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. |
| 4) Sept 27: 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 |
| 5) Sep 29: 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. |
| 6) Oct 4: Approximation algorithms via
Linear Programming. |
Lec 6 notes. |
Design
of Approximation Algorithms by Williamson and Shmoys.
(Online book). |
| 7) Oct 6: 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 7 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. |
| 8) Oct 11: Decision making under total
uncertainty: Multiplicative Weights Update algorithm. |
Lec 8 notes. |
Arora,
Hazan, Kale survey. |
| 9) Oct 13: High-dimensional geometry, Curse
of Dimensionality, and Dimension Reduction. |
Lec 9 notes. |
Jelani Nelson's lecture
notes on Dimension Reduction. (Also has discussion of
faster versions.) He prefers these newer and more extensive notes. |
| 10) Oct 18: Random walks, Markov
Chains, and how to analyse them.Also, Markovian
Models. |
Lec 10 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. |
| 11) Oct 20: Intrinsic dimensionality of data
and low-rank matrix approximations (SVD). |
Lec 11 notes. |
Paper on Latent
Semantic Analysis |
| 12) Oct 25: SVD, Power Method, and Recovering
Stochastic Block Models. (+ glimpses of eigenvalues of random matrices) |
Lec 12 notes. |
Topics
in Random matrix theory by T. Tao. For more coverage see Introduction to Random Matrices (by Anderson, Guionnet, and Zeitouni). |
| 13) Oct 27: Semidefinite Programming (SDP)
and Approximation Algorithms. |
Lec 13 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) |
| 14) Nov 8:
Going with slope: offline, online, and randomly. (Various
flavors of gradient descent.) |
Lec 14 notes.
(Thanks to Ariel Schwartzmann Cohenca for updating last
year's notes.) |
The
Zen of Gradient Descent (blog post by Moritz Hardt) |
| 15) Nov 10:Oracles, Ellipsoid Method, and
their uses in Convex Optimization. |
Lec 15 notes. Santosh Vempala's notes have more detailed analysis. |
Amusing NY
Times article on discovery of Ellipsoid Method. (copyright
NY Times) |
| 16) Nov 15: Submodular Functions and Lovasz Extension. | Lec 16 notes. |
Shaddin Dughmi's Survey on Submodular Functions and their Various Extensions |
| 17) Nov 17: Games, Min-Max and Equilibria (Von Neumann's Min-Max, Zero Sum Games, Nash Equilibria in General Games) |
Lec 17 notes. |
|
| 18) Nov 21: Protecting information against
loss: Intro to Coding Theory. |
Lec 18 notes. |
Modern
Coding Theory by Richardson and Urbanke. |
| 19) Nov 29: Tensor Methods |
Lec 19 notes. |
Blog Post by Rong Ge on Off Convex Blog: Tensor Methods in Machine Learning by Rong Ge. |
| 20) Dec 1: Counting and Sampling Problems. |
Lec 20 notes |
Eric
Vigoda's lecture notes on this topic from 2006. |
| 21) Dec 6: Taste of Cryptography: Secret
Sharing and Multiparty Computation. |
Lec 21 notes. |
Principles
of Modern Cryptography by Dan Boneh. |
| 22) Dec 8: Heuristics: Algorithms we don't
yet know how to analyse. |
Lec 22 notes. |
|
| 23) Dec 13: Differential Privacy (Guest Lecture by Mark Bun) |
Lec 23 notes. |
|
| 24) Dec 15: Part 1: Real-life environments
for big-data computations (MapReduce etc.) Part 2:
Ask Sanjeev Anything |
Lec 24 notes. |
Single file of all course notes, home works
and final from 2015.
(you can refer to this; updated lecture notes will be posted
below)
(Schedule is similar
to 2015 with small changes.)
Description/guidelines to term
project