Princeton University logo
Princeton University
Computer Science Department

Computer Science 521
Advanced Algorithm Design

Sanjeev Arora

  Fall 2014

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 4-5 homeworks over the semester, which may 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 13:30-15:00   Room: Small Auditorium, CS Building. First meeting: Sept 11.

Instructor: Sanjeev Arora- 307 CS Building - 609-258-3869 arora AT the domain name

Teaching assistant: Kevin Lai, Room 003.    


Office hrs: Sanjeev: Tues-Thurs 3-4pm.
                    Kevin:  Mon-Wed: 5-6pm. (On Mondays before HW is due, will be an open Q&A session in a classroom.)                     


  1. HW 1: Out Sept 25, Due: Oct 2. 
  2. HW2: Out Oct 7, Due: Oct 16.
  3. HW3: Out Oct 23, Due: Nov 10.
  4. HW4: Out Nov 12, Due: Dec 2. Image file for SVD question.
  5. HW5: Out Dec 5, Due: Dec 13.

Lecture notes + readings

Single file of all course notes, home works and final.

(Schedule is similar to 2013 with minor changes.)

Lecture number + Title
Required reading
Further reading + links
1) (Sept 11) How is this course different from undergrad algorithms?
   Hashing Part 1.
Lecture 1 notes.
Motwani-Raghavan's chapter.
For further interesting applications look up advanced hashing such as
bloom filters, cuckoo hashing.
2) (Sept 16) Karger's min cut algorithm (and its extensions).A simple and gorgeous intro to randomized algorithms.
Lecture 2 notes
(includes extracts from lecture notes of S. Dasgupta and E. Vigoda)

3) (Sept 18) Deviation bounds and their applications.
Bounds by Markov, Chebyshev and Chernoff on how much and how often a random variable deviates from its expectation. Applications to Load Balancing and sampling.
Lecture 3 notes.

Survey of concentration inequalities by Chung and Lu
4) (Sept 23) Stable matchings, stable marriages and price of anarchy. Guest lecture by Mark Braverman.
Lecture 4 notes.
(scribe: Naman Agrawal)
Includes audio; slow download.

5) (Sept 25) Hashing to real numbers and its big-data applications. Estimating the size of a set that's too large to write down. Estimating the similarity of two documents using their hashes. Lecture 5 notes.

6) Sept 30: Linear thinking. (Linear modeling, linear equations and inequalities, linear programming.  Examples from econometrics, machine learning, etc.)
Lecture 6 notes .
Also see section 7.1 of relevant chapter from Dasgupta, Papadimitriou, Vazirani (ugrad text).

Analysis of Gaussian elimination (notes by Peter Gacs)
7) (Oct 2) Provable Approximation via Linear Programming.
(Min vertex cover, MAX-2SAT, Virtual Circuit routing)
Lecture 7 notes.

8) (Oct 7) Decision-making under uncertainty: Part 1.
Basics of rational choice theory. Optimal decision via dynamic programming. Markov Decision processes (MDPs) and stationary solutions via LP.
Lecture 8 notes.

This old article may still be useful if you want to read more.
Wikipedia page has many pointers.
Lots of other material on the web but everything is very notation-heavy.
(Informal) Five commandments about decision theory.
For those with further interest in MDPs, there's   Andrew Moore's notes  and Jay Talor's excellent survey
8) (Oct 9) Decision making under total uncertainty.
(Hint: Minimize your regret!)
Lecture 9 notes.
Arora-Hazan-Kale survey.
10) (Oct 14) Using multiplicative weights for LP solving,
Game Playing, and Portfolio Management. (+ glimpses of duality)
Lecture 10 notes. Papers cited in the notes.
Wikipedia entry on the traditional stock
pricing theory.
11) Oct 16): Taking it to the next dimension...
High dimensional geometry. Curse (and blessing) of Dimensionality. Dimension reduction.

Lecture 11 notes.
Examples of high dimensional data
by G. Allen.
12 Oct 21): Random walks, Markov Chains, and Analysis of convergence. Also, Markovian models.
Lecture 12 notes.

13) Oct 23): Finding true dimensionality of datasets, low-rank matrix approximation, and SVD.
Lecture 13 notes

14) Nov 4): Computing SVD, Power Method, Recovering planted bisections. (Glimpses of eigenvalues of random matrices.)
Lecture 14 notes.
SVD chapter in Hopcroft-Kannan book.
15) Nov 6) Semidefinite Programming and Approximation Algorithms. 0.878-algorithms for MAX-CUT and MAX-2SAT, and the saga of the 0.878. Lecture 15 notes.
16) Nov 11): Following the slope: Gradient Descent.
Convex optimization: Offline, Online, Stochastic. Getting rich by managing portfolios in an online fashion.
Lecture 16 notes.
17) Nov 13): Oracles, Ellipsoids, and their uses for convex optimization.
(including solving LPs too big to write down)
Lecture 17 notes.
Santosh Vempala's notes.
18) Nov 18): Minmax theorem and duality.  Zero Sum Games and MinMax theorem.
Lecture 18 notes.

19) Nov 20) A taste of algorithmic game theory.
Nash equilibria, price of anarchy, correlated equilibria.
Lecture 19 notes.

20) Nov 25)  Protecting against information loss: coding theory. Lecture 20 notes.

21) Dec 2): Counting and sampling problems and their close interrelationship.
Valiant's class #P. Monte Carlo method. Dyer's algorithm for counting knapsack solutions.
Lecture 21 notes.
Eric Vigoda's notes (Has FPRAS'es for three problems)
22) Dec 4): A taste of cryptography: secret sharing and secure multiparty computation. Lecture 22 notes

23) Dec 9): Real-life systems for big-data algorithms: Mapreduce etc. (Guest lecturer Kai Li) Lecture 23 notes.
(coming soon)
Kai Li's slides. A few slides by David Gleich on the programming model.
Some program examples from Jeff Phillips, who has an entire course devoted to big data algorithms.
(See also Jelani Nelson's course.)
24) Dec 11): Heuristics: Algorithms we don't yet know how to analyse.
Lecture 24 notes.

Term Project 

Description/guidelines to term project.

You have a choice between the term project or the takehome final.

Sample Final Projects (Fall 2014)
  1. Dynamic Learning Rate Adjustment Algorithm by Brian Bullins, Sergiy Popovych, Hansen Zhang.
  2. K-median algorithms: theory in practice by David Dohan, Stefani Karp, Brian Matejek. 
  3. Semi-supervised learning in Support Vector Machines by Sachin Ravi. 
  4. Estimating trending topics on Twitter with small subsets of the total data, by Evan Miller, Kiran Vodrahalli and Albert Lee.

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.

Readings for Friday Section

(for students who come to the Friday meetings)