Computer Science 521
(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.
Instructor: Sanjeev Arora- 307 CS Building - 609-258-3869 arora AT the domain name cs.princeton.edu
Teaching assistant: Kevin Lai, Room 003.
ENROLLED STUDENTS SHOULD ADD THEMSELVES TO THE DISCUSSION LIST AT
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.)
Single file of all course notes, home works
(Schedule is similar
to 2013 with minor changes.)
|Lecture number + Title
||Further reading + links
|1) (Sept 11) How is this course different
from undergrad algorithms?
Hashing Part 1.
|Lecture 1 notes.
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
||Lecture 2 notes
(includes extracts from lecture notes of S. Dasgupta and E. Vigoda)
|3) (Sept 18) Deviation bounds and their
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.
of concentration inequalities by Chung and Lu
|4) (Sept 23) Stable matchings, stable
marriages and price of anarchy. Guest lecture by Mark
||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
||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
(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.
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
(Hint: Minimize your regret!)
|Lecture 9 notes.
|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
|11) Oct 16): Taking it to the next
High dimensional geometry. Curse (and blessing) of Dimensionality. Dimension reduction.
of high dimensional data
by G. Allen.
|12 Oct 21): Random walks, Markov Chains,
and Analysis of convergence. Also, Markovian models.
|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.)
||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:
Convex optimization: Offline, Online, Stochastic. Getting rich by managing portfolios in an online fashion.
|17) Nov 13): Oracles, Ellipsoids, and
their uses for convex optimization.
(including solving LPs too big to write down)
|18) Nov 18): Minmax theorem and
duality. Zero Sum Games and MinMax theorem.
|19) Nov 20) A taste of algorithmic game
Nash equilibria, price of anarchy, correlated equilibria.
|20) Nov 25) Protecting against information loss: coding theory.||Lecture 20
|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.
||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
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.
to term project.
(for students who come to the Friday meetings)