COS 521

Advanced Algorithm Design

Princeton University

Instructor: Matt Weinberg

TA: Divyarthi Mohan

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

Piazza: https://piazza.com/class/j7dw724yuexg7

Announcements will be posted below:

Project Guidelines: initial proposal due 11/30 (optional).

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. To submit your homework, email it to Divya at dm23 (at) cs (dot) Princeton (dot) edu by the deadline with subject line "COS 521 HW X."

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/14	Hashing	Lecture Notes 1
9/19	Randomized Min-Cut	Lecture Notes 2
9/21	Concentration Bounds	Lecture Notes 3
9/26	Hashing to Reals	Lecture Notes 4
9/28	Linear Programs	Lecture Notes 5
10/3	LP Rounding	Lecture Notes 6 (slightly different from last year)
10/5	LP Duality	Lecture Notes 7 (different from last year)
10/10	Decisions under Uncertainty	Lecture Notes 8
10/12	Learning from Experts	Lecture Notes 9
10/17	Dimensionality Reduction	Lecture Notes 10
10/19	Markov Chains	Lecture Notes 11
10/24	Low-Rank Approximations	Lecture Notes 12
10/26	SVD and Stochastic Block Model	Lecture Notes 13
10/31	Fall Break
11/2	Fall Break
11/7	Semidefinite Progamming	Lecture Notes 14
11/9	Ellipsoid Algorithm	Lecture Notes 15 (slightly different from last year)
11/14	Submodular Minimization	Lecture Notes 16
11/16	Game Theory: Equilibria	Lecture Notes 17 (slightly different from last year)
11/21	Combinatorial Auctions I	Lecture Notes 18
11/23	Thanksgiving
11/28	Combinatorial Auctions II	Lecture Notes 19
11/30	Communication Complexity	Lecture Notes 20
12/5	Gradient Descent (Guest Lecture: Sanjeev Arora)	Lecture Notes 21
12/7	Differential Privacy (Guest Lecture: Mark Bun)	Lecture Notes 22
12/12	Coding Theory	Lecture Notes 23
12/14	Online Algorithms	Lecture Notes 24