Princeton University
|
Computer Science 521
|
Fall 2014
|
(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
PIAZZA.COM
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
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. |
Description/guidelines
to term project.
(for students who come to the Friday meetings)
