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 programming-based exploration of the lecture ideas (60% of grade). Choice of take-home 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)
Lectures: Tuesday & Thursday 3:00pm-4:20pm in Friend Center 004.
Office Hours: Pravesh: Immediately after class, 194 Nassau St, Room 219.
Christopher: Immediately after class, Friends 004.
Sixue: Wed. 7:00-8:00pm, 194 Nassau St, Room 307.
Sobhan: Fri. 2:00-3: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 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 grading policy).
|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.||
|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.|
|10. 10/16||The Johnson-Lindenstrauss 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||Low-rank 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.|
|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|
|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|