COS 521

Advanced Algorithm Design

Princeton University

Instructor: Matt Weinberg

TAs: Meryem Essaidi, Dingli Yu

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://us.edstem.org/courses/107/discussion/. Enroll using the enroll code: https://us.edstem.org/join/JaXjsT.

Announcements will be posted below:

- Use the enroll code 521StudentFA19 to enroll in the course on MTA.

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 Mechanical TA here.

PS1 is now available here. Submit to MTA by 9/30 at 11:59pm.

PS2 is now available here. Submit to MTA by 10/14 at 11:59pm.

PS3 is now available here. Submit to MTA by 11/4 at 11:59pm.

PS4 is now available here. Submit to MTA by 11/18 at 11:59pm.

PS5 is now available here. Submit to MTA by 12/9 at 11:59pm.

Final is now available here. Follow submission instructions in the PDF.

Final Exam/Project Guidelines: here.

Lecture Notes: We will use lecture notes from previous iterations, and mostly follow the same schedule. You can get a headstart on the lecture notes here (along with optional deeper reading material), and notes will be posted below as the schedule becomes finalized.

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