Princeton COS 521
Advanced Algorithm Design

Graduate algorithms course covering advanced topics such as randomness, continuous optimization, spectral methods, high dimensional geometry, approximation algorithms and diverse applications of algorithmic tools and thinking.

Instructor: Pravesh K. Kothari (kothari AT cs.princeton.edu)


Course Summary

Material: COS 521 gives a broad exposure to algorithmic advances of the past few decades, preparing students to read and understand research papers in algorithms. Course is suitable for graduate students (including those not in CS) and advanced undergrads.

Prerequisites: One undergraduate course in algorithms (e.g., COS 423), or equivalent mathematical maturity. Listeners and auditors are welcome with prior permission.

Coursework: Two lectures per week. 4 homeworks (55% of grade). Choice of take-home final, or a term project in groups (40% of grade). Participation (in class and peer grading) (5% of grade). See course information for more details.

Peer Grading: We will use Gradescope for submission and grading of homeworks. You will grade each others' assignments. Your grade on the homeworks will be determined by peer evaluation. Evaluating your peers' assignments has pedagogical value, especially to the grader (you will write better solutions if you have experience evaluating them), but also to the gradee. Homeworks for this class can be long/challenging and the class is large. This will give the (peer and TA) graders an opportunity to provide thorough feedback for some instead of rushed feedback for everyone. We will encourage graders to focus on providing thorough text feedback. Every submission will be graded by someone. Some (randomly selected) homeworks will be graded by a TA. You will have the opportunity to appeal grades, in case there is a major mistake. The final (exam and project) will be graded exclusively by the TAs and the instructor.

Resources: There is no official text -- we will use our own lecture notes and assorted online resources. Please see course webpages from previous years for additional material.

Homework
Homework 1 (due Sunday, Sep 29, 11:59pm)
Homework 2 (due Sunday, 11:59pm, Oct. 27th)
Homework 3 (due Sunday, 11:59pm, Nov 17th)

Homework 4 (due Monday, 11:59pm, Dec 4th)


Administrative Information

Lectures: M/W 1:30 pm to 2:50 pm in Friend Center 006.

TAs: Amrit Daswaney (Amrit) ad6919 AT cs.princeton.edu
Siyang Wu (Siyang) - sw2776 AT princeton.edu.

Office Hours: Pravesh: M/W, 3-4pm, CS 320.
Amrit: Thu (10:30 am - 12:30 pm), COS 003
Siyang: Thu (6:00 - 7:00 pm) and Tue (1:30 pm - 2:30 pm) COS 003

Ed: Course discussion and questions will be managed through Ed App. If you are not already added, please email the instructor.

Homework: Homeworks will be due on Sundays at 11:59pm and assigned well before the due date. Handwritten solutions will not be accepted. Instead, we require students to prepare problem sets in LaTeX. You may (but are not required to) use this template. An online latex system such as Overleaf may be helpful.

Some assignments will feature bonus problems. Bonus problems will often be chosen to give you a taste of current algorithms research. They will not be directly added to the assignment score although high success on bonus problems may improve your final grade.

For regular homework problems collaboration is allowed, but solutions must be written-up individually. Students must list collaborators for each problem separately, or write "No Collaborators" if you worked alone. Collaboration is not allowed on bonus problems (see course information).

Final Project See Project Guidelines for details of the final exam/project.

-->
Lecture # Topic Required Reading Optional Reading
Power of Randomization in Algorithms
1. 9/4 Randomized Minimum Cut Lecture 1 notes. Karger's original paper in all its glory is here and here is the Karger-Stein variant. Here's a linear time algorithm, also due to Karger that builds on this idea along with a cool new tool of tree packings (subject of much recent research in combinatorics too, see e.g., here!). There are several works on using min cut like procedures for clustering like applications. We will also see other approaches to clustering vertices of a graph in the future lectures. In the meantime, here's a paper on using min cuts for segmentation.
2. 9/9 Basic Probability Lecture 2 notes. For a general ``feel" of what kind of concentration inequalities could hold and to see Chernoff bounds in proper context, I recommend reading the introduction (Section 1.2, specifically) of Ramon Von Handel's fantastic notes.
3. 9/11 Hashing and Graph Sparsification Lecture 3 notes. Three lectures on graph sparsification by Nikhil Srivastava at the Simons Institute.
LPs, SDPs and Applications
4. 9/16 Linear Thinking Lecture 4 notes. A New York Times article on Khachiyan's discovery of polynomial time algorithms for LP (and an erroneous conclusion that amounts to it implying P=NP).
5. 9/18 Approximation Algorithms via Linear Programming Lecture 5 notes.
6. 9/23 LP Duality and Applications Lecture 6 notes.
7. 9/25 Semidefinite Programming and Approximating Maximum Cuts Lecture 7 notes.
  • Good reference on applications of semidefinite programming.
  • DIMACS notes on limits of approximation algorithms and the unique games conjecture.
Numerical Methods
8. 9/30 Oracles, Ellipsoid Method and Convex Optimization Lecture 8 notes.
  • Nisheeth Vishnoi's excellent lecture notes on convex optimization, including the ellipsoid method. These cover many details we don't have time for in this course!
  • New York Times article from 1984 on the discovery that the Ellipsoid method can solve linear programs in polynomial time.
9. 10/02 Dimension Reduction and Johnson Lindenstrauss Lemma Lecture 9 notes.
  • Recent paper that essentially resolves the optimality of the Johnson-Lindenstrauss lemma for preserving distances.
10. 10/7 Introduction to Spectral Methods Lecture 10 notes
  • Check out Chapter 10 in these notes for a discussion of methods faster than power method.
  • Daniel Spielman's lecture notes on spectral methods for the stochastic block model.
Algorithms in the Real World
11. 10/09 Differential Privacy Lecture 11 notes
12. 10/21 Compressive Sensing Lecture 12 notes
  • Webpage on Sparse Fourier Transform algorithms.
  • Princeton course on compressed sensing and related topics.
13. 10/23 Introduction to Coding Theory Lecture 13/14 notes
14. 10/28 Reed Solomon Codes Ctd. Lecture 13/14 notes
  • Madhu Sudan's Coding Theory Class
15. 10/30 Random Walk, Markov Chains and How to Analyze Them Lecture 15 notes
16. 11/04 Counting and Sampling Problems Lecture 16/17 Notes
17. 11/06 Counting and Sampling Problems Lecture 16/17 Notes
Beyond the Worst-Case Analysis
18. 11/11 Average Case Models: Planted Partition via Random Matrices Lecture 18 Notes
19. 11/13 Matrix Concentration and the Planted Clique Problem Lecture 19 Notes
20. 11/18 Spectral Graph Sparsification Lecture 20 Notes