Princeton University logo
Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design

Sanjeev Arora

Pravesh Kothari

  Fall 2016

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

Administrative Information

Lectures: Tues-Thurs 13:30-15:00   Room: Friend E-quand A224. First meeting: Sept 15.

Instructor: Sanjeev Arora (307 CS Building - 609-258-3869 arora AT the domain name
                    Pravesh Kothari (219, CS Building, 609-258-8014, Email: kothari AT cs

Teaching assistant: Fermi Ma ( fermim @ princeton . edu )


Office hrs: Sanjeev: Tues-Thurs 15:00-16:00.
Pravesh: Tues-Thurs 15:00-16:00


    Homework 1 (Due: Friday, Sep 30)
    Homework 2 (Due: Oct 21)
    Homework 3 (Due: Nov 8)
    Homework 4 (Due: Dec 16)

Lecture notes + readings

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

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.