Grading
- 20% Midterm 1
- 20% Midterm 2
- 30% Final Exam
- 30% Homework Assignments
- +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 | Flow Applications: Bipartite Matching | slides | ||
| Fr | 2/7 | Max Flow with Clever Augmenting Paths | slides | ||
| Tu | 2/11 | More Flow Applications | slides | ||
| Fr | 2/14 | Midterm 1 | |||
| Tu | 2/18 | Linear Programming: Basics, Applications | slides | ||
| Fr | 2/21 | Linear Programming | slides | ||
| Tu | 2/25 | Edge Coloring | slides | ||
| Fr | 2/28 | No class | |||
| Tu | 3/4 | Spring Break | |||
| Fr | 3/7 | Spring Break | |||
| Tu | 3/11 | Multiplicative Weights (Experts) | slides | notes, MWU proof (by Saranurak) | |
| Fr | 3/14 | Multiplicative Weights (Solving LPs) | slides | notes (by Saranurak) | |
| Tu | 3/18 | Intractability | slides | ||
| Fr | 3/21 | Intractability II: Reductions | slides | ||
| Tu | 3/25 | Randomization in Algorithms | slides | ||
| Fr | 3/28 | Randomization in Algorithms | slides | ||
| Tu | 4/1 | Midterm 2 | |||
| Fr | 4/4 | Approximation Algorithms I (Vertex/Set Cover) | slides | ||
| Tu | 4/8 | Approximation Algorithms II (TSP) | slides | ||
| Fr | 4/11 | Approximation Algorithms III (k-Center, Subset Sum) | slides | ||
| 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