Princeton COS 521
Advanced Algorithm Design
Capstone graduate algorithms course covering advanced topics such as randomness, optimization, and high dimensional geometry. We also explore diverse applications of algorithmic tools and thinking.
Instructors: Pravesh Kothari, Christopher Musco
Course Summary
Material: COS 521 gives a broad yet deep 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. 5 homeworks, including some simple programmingbased exploration of the lecture ideas (60% of grade). Choice of takehome final in January, or a term project in groups of two (40% of grade). For specific policy on grading, late assignments, etc. please see the grading policy sheet.
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 (Blackboard submission link):
Homework 1 (due Monday, Oct. 8th)
Homework 2 (due Friday, Oct. 26th)
Homework 3 (due Monday, Nov. 19th)
Homework 4 (due Friday, Dec. 7th, stockData.csv, stockData.mat, stockNames.csv)
Homework 5 (due Friday, Jan. 11th)
Exam
48 hour take home final.
Released: Jan. 16th,
Due: Jan. 21st
Administrative Information
Lectures: Tuesday & Thursday 3:00pm4:20pm in Friend Center 004.
Teaching Assistants: Sixue Liu (Cliff)  sixuel@cs.princeton.edu, Seyed Sobhan Mir Yoosefi (Sobhan)  syoosefi@cs.princeton.edu.
Office Hours: Pravesh: Immediately after class, 194 Nassau St, Room 219.
Christopher: Immediately after class, Friends 004.
Sixue: Wed. 7:008:00pm, 194 Nassau St, Room 307.
Sobhan: Fri. 2:003:00pm, 35 Olden St, Room 431.
Piazza: Course discussion and questions will be managed through Piazza. Please sign up here.
Homework: We require students to prepare problem sets in LaTeX.
You can use this template. Submission is managed through Princeton's Blackboard system. A compiled PDF of your
homework should be uploaded by 11:59pm on the due date.
For regular homework problems collaboration is allowed, but solutions must be
writtenup 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 grading policy).
Final Project Read the Final Project Guidelines Here.
Deadlines Preliminary Proposal: Dec. 5
Final Proposal: Dec. 14
Presentation: Jan. 15, 3pm  5pm
Final Reports: Jan. 15
Final project reports from 2014 here.
Lecture #  Topic  Required Reading  Optional Reading 

Randomness and Hashing  
1. 9/13  Hashing  Lecture 1 notes.  
2. 9/18  Randomized Minimum Cut  Lecture 2 notes.  
3. 9/20  Concentration Bounds  Lecture 3 notes.  
4. 9/25  Hashing to Reals  Lecture 4 notes. 

Linear Thinking  
5. 9/27  Linear Thinking  Lecture 5 notes. 

6. 10/2  LP Relaxations & Approximation Algorithms  Lecture 6 notes. 

7. 10/4  LP Relaxations Continued 


8. 10/9  Linear Programming Duality  Lecture 8 notes.  
9. 10/11  Learning from Experts: Multiplicative Weights Algorithm  Lecture 9 notes. 

Dimensionality Reduction  
10. 10/16  The JohnsonLindenstrauss Lemma  Lecture 10 notes. 

11. 10/18  Approximate regression, εnets, fast JL 
Lecture 11 notes. 

12. 10/23  Nearest Neighbor Search  Lecture 12 notes. 

13. 10/25  Lowrank Approximation and SVD  Lecture 13 notes. 

10/30  No Class, Fall Recess  
11/1  No Class, Fall Recess  
14. 11/6  Power Method and and Spectral Clustering  Lecture 14 notes. 

Optimization  
15. 11/8  Gradient Descent  Lecture 15 notes. 

16. 11/13  Ellipsoid Method (+ online and stochastic GD)  Lecture 16 notes. 

17. 11/15  Interior Point Methods  Lecture 17 notes. 

18. 11/20  Semidefinite Programming  Lecture 18 notes. 

11/22  No Class, Thanksgiving  
Select Topics  
19. 11/27  Random Walks, Markov Chains and How to analyze them  Lecture 19 Notes  
20. 11/29  Counting and Sampling Problems  Lecture 20 Notes  
21. 12/4  Compressed Sensing  Lecture 21 notes.  
22. 12/6  Coding Theory  Lecture 22 notes.  
23. 12/11  A Taste of Cryptography: Secure Multiparty Computation  Lecture 23 Notes 

24. 12/13  Heuristics: Algorithms we don't yet know how to analyze  Lecture 24 notes 