Princeton University
|
Computer Science 521
|
Fall 2013
|
(Important: In light of the new grad course requirements, this course is changing as of 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, and they will be graded on a different curve. Grads who intend to specialize in theoretical CS are invited to attend extra discussions (at Small World coffee on Friday afternoon) that explore some topics in greater depth.
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 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.) There will be a take-home final in January. Grads not specializing in theoretical CS will be allowed to substitute a course project (done in groups of 2) + one extra homework for the final. There is no official text. Instead, we will use assorted online resources. Students will be expected to scribe lecture notes once or twice during the term.
Instructor: Sanjeev Arora- 307 CS Building - 609-258-3869 arora AT the domain name cs.princeton.edu
Teaching assistant: Aman Dhesi adhesi AT the domain
name cs.princeton.edu
ENROLLED STUDENTS SHOULD ADD THEMSELVES TO THE DISCUSSION LIST AT
PIAZZA.COM
Office hrs: Sanjeev Monday 3:30-5pm in Room 307 and by
appointment.
Aman Wed 12-1:30pm
1. Hash for breakfast, lunch and
dinner. (2 lectures)
2. Power of randomized choices.
(2 lectures)
3. Linear programs to find
solutions to life's constraints. (1 lecture)
4. Approximation as a workaround
for intractability: Part 1. (1 lecture)
5. Play a game, manage your
riches ---no regret! (2 lectures)
6. Looking at a problem in more
than one way: duality. (2 lectures)
7. Expand your mind: taking
things to a higher dimension. (1 lecture)
"The key to growth is introduction of higher dimensions of
consciousness.." [LaoTzu]
8. How to swim against the
stream: sketches of big data. (1 lecture)
9. The power of the spectrum:
random walks, clustering, graph decomposition. (2 lectures)
10. Solving a linear program
including LPs too big to write down. (sketch). (1 lecture).
11. Feasible approaches to
nonlinear problems: Semidefinite
programs. (1 lecture)
12. Metric spaces and how to
think about them. (2 lectures)
13. Algorithms that don't always
work: Heuristics. (2 lectures)
MCMC. Local
search/gradient descent. SAT
Solvers.
14. How to do many things at once: multiprocessing (1 lecture)
15. Algorithmic
view of modeling (1 lecture)
16. Algorithms
in machine learning.
| Lecture number + Title |
Required reading |
Further reading + links |
| 1) (Sept 12) How is this course different
from undergrad algorithms? Hashing Part 1. |
Lecture 1
notes. |
|
| 2) 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) 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) 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 4
notes. |
|
| 5) Sept 24: Linear thinking. (Linear
modeling, linear equations and inequalities, linear
programming. ) |
Lecture 5 notes .
|
Also see section 7.1 of
relevant chapter from Dasgupta, Papadimitriou,
Vazirani (ugrad text). Analysis of Gaussian elimination (notes by Peter Gacs) |
| 6) Provable Approximation via Linear
Programming. (Min vertex cover, MAX-2SAT, Virtual Circuit routing) |
Lecture 6 notes. |
(for students who come to the Friday meetings)
| Date and topic |
Reading |
Additional reading/links |
| 1) Random graph theory, indep. set in random
graphs, random 3SAT. |
||