Grading
- 20% Midterm 1
- 20% Midterm 2
- 30% Final Exam
- 30% Homework Assignments (5 HWs)
- +5% Active Participation
Schedule
| # | WD | Date | Topics | References | Notes |
|---|---|---|---|---|---|
| Tu | 1/7 | Introduction + Stable Matching | slides | ||
| Fr | 1/10 | Greedy Algorithms: Interval and Minimum Lateness Scheduling | slides | HW1 Posted | |
| Tu | 1/14 | No Class | |||
| Fr | 1/17 | Greedy Algorithms + Intro to Graphs: MST | slides | ||
| Tu | 1/21 | MST Cost Estimation in Sublinear Time | slides | ||
| Fr | 1/24 | Dynamic Programming: WIS, Edit Distance, LIS | slides | ||
| Tu | 1/28 | Dynamic Programming: Approximate Edit Distance | slides | ||
| Fr | 1/31 | Maximum Flow | slides | ||
| Tu | 2/4 | Maximum Flow | |||
| Fr | 2/7 | Maximum Flow Applications | |||
| Tu | 2/11 | Maximum Flow Applications | |||
| Fr | 2/14 | Midterm 1 | |||
| Tu | 2/18 | Linear Programming | |||
| Fr | 2/21 | Linear Programming | |||
| Tu | 2/25 | Multiplicative Weights | |||
| Fr | 2/28 | Multiplicative Weights | |||
| Tu | 3/4 | Spring Break | |||
| Fr | 3/7 | Spring Break | |||
| Tu | 3/11 | Intractability | |||
| Fr | 3/14 | Intractability | |||
| Tu | 3/18 | Randomization in Algorithms | |||
| Fr | 3/21 | Randomization in Algorithms | |||
| Tu | 3/25 | Randomization in Algorithms | |||
| Fr | 3/28 | Randomization in Algorithms | |||
| Tu | 4/1 | Midterm 2 | |||
| Fr | 4/4 | Approximation Algorithms | |||
| Tu | 4/8 | Approximation Algorithms | |||
| Fr | 4/11 | Sublinear Algorithms | |||
| Tu | 4/15 | Sublinear Algorithms | |||
| Fr | 4/18 | Sublinear Algorithms | |||
| Tu | 4/22 | Final Exam |
Resources
There is no official textbook that includes all the material of this class. The following, however, is a list of helpful supplementary resources.
- [KT] Jon Kleinberg and Éva Tardos. Algorithm Design.
- [E] Jeff Erickson. Algorithms (available free electronically).
- [CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms.
- N. Alon and J. Spencer, The probabilistic method
- S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities
- B. Doerr, Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
- A. Czumaj and C. Sohler, Sublinear-time algorithms
- R. Rubinfeld and A. Shapira, Sublinear Time Algorithms
- O. Goldreich, Introduction to Property Testing
- A. McGregor, Graph Stream Algorithms: A Survey
- T. Roughgarden, Communication Complexity (for Algorithm Designers)
- D. Woodruff, Sketching as a Tool for Numerical Linear Algebra
- A. Bhattacharyya and Y. Yoshida, Property Testing