Princeton University logo
Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design
  

Sanjeev Arora


  Fall 2015

Course Summary

(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.

Administrative Information

Lectures: Tues-Thurs 15:00-16:30   Room: Friend 006. First meeting: Sept 17.

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.
                                       




Homeworks

  1. HW1. Out: Sept 29. Due Oct 9.
  2. HW2. Out: Oct 13. Due Oct 23.
  3. HW3. Out: Oct 29. Due Nov 13.
  4. HW4. Out Nov 19. Due Dec 4. Image file for Qs 2.
  5. HW 5. Out Dec 18; Due Jan 8.



Lecture notes + readings

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.



Term Project 

Description/guidelines to term project 


Resources and Readings


Further reading (books)

This course presents "greatest hits" of algorithms research and/or "must-know foundational ideas."  Usually the topics are covered in greater detail in specific textbooks.  Here are some great resources for additional reading:
  1. Randomized Algorithms by Motwani and Raghavan.
  2. Online computation and online analysis by Borodin and El-Yaniv.
  3. Probabilistic Method by Alon and Spencer.
  4. Approximation algorithms by Vijay Vazirani.
  5. Design of approximation algorithms (legal download) by Williamson and Shmoys
  6. Spectral graph theory by Fan Chung.
  7. Mining of massive datasets by Rajaraman, Leskovec, Ullmann.
  8. Algorithmic Game Theory (nonprintable legal version) by Nisan, Roughgarden, Tardos, Vazirani.
  9. Reversible Markov Chains and Random Walks on Graphs. By Aldous and Fill.


Readings for Friday Section

(for students who come to the Friday meetings)