COS 521

Advanced Algorithm Design

Princeton University

Instructors: Mark Braverman, Matt Weinberg

TAs: Linda Cai, Zhou Lu

For contact information, course description, collaboration/grading policy, etc., please see the course infosheet.

Ed: We will use Ed for course discussion. The link is: https://edstem.org/us/courses/8773/discussion/. If you are enrolled in the course, you should have access to Ed. Please email the instructors if you cannot access Ed.

codePost: Course assignments will be submitted to codePost. You can enroll in the course using this link (must use an @princeton or @cs.princeton email address).

Announcements will be posted below:

- Guidelines for the final exam/project are posted: final guidelines.

Homework: Homeworks will be posted below when they become available. Here is a LaTeX template you may use for the homework, and here is a short guide to LaTeX. Feel free to visit office hours for help installing/setting up LaTeX. Submit your homework through codePost here.

Lecture Notes: We will use lecture notes from previous iterations, and mostly follow the same schedule. Below is a tentative schedule:

Date	Topic	Reading Material
9/2	Randomized Min-Cut	Lecture Notes 1
9/7	LP Rounding I	Lecture Notes 2
9/9	LP Rounding II	Lecture Notes 3
9/14	LP Duality	Lecture Notes 4
9/16	Semi-Definite Programs	Lecture Notes 5
9/21	Hashing	Lecture Notes 6
9/23	Concentration Inequalities	Lecture Notes 7
9/28	Martingales	See Ed
9/30	Random Walks and Markov Chains	Lecture Notes 9
10/5	Multiplicative Weights	Lecture Notes 10
10/7	Johnson-Lindenstrauss	Lecture Notes 11
10/12	Locality-Sensitive Hashing and Approximate Nearest Neighbors	Lecture Notes 12
10/14	Low-Rank Approximations and SVD	Lecture Notes 13
10/19	Fall Break
10/21	Fall Break
10/26	Coding Theory	Lecture Notes 14
10/28	Online Algorithms I	Lecture Notes 15
11/2	Online Algorithms II	Lecture Notes 16
11/4	Computation of Nash	Lecture Notes 17
11/9	Ellipsoid Algorithm	Lecture Notes 18
11/11	Submodular Minimization	Lecture Notes 19
11/16	Communication Complexity	Lecture Notes 20
11/18	Hashing to Reals	Lecture Notes 21
11/23	Differential Privacy	Lecture Notes 22
11/25	Thanksgiving Break
11/30	Combinatorial Auctions I	Lecture Notes 23
12/2	Combinatorial Auctions II	Lecture Notes 24