COL758: Advanced Algorithms
- Week 1: Matroids, greedy algorithm.
Notes by Michel Goemans
Notes by Jeff Erickson
- Week 2: Matroid Intersection, Gradient Descent
My notes on matroid intersection.
- Week 3: Gradient Descent, Online Gradient Descent
Lecture notes by Nisheeth Vishnoi
Lecture Notes on Gradient Descent in Sanjeev Arora's course (read for Q4 in Homework #1)
- Week 4: Online Gradient Descent, Multiplicative Update Method
Survey on multiplicative update method by Arora, Hazan, Kale
- Week 5: Multiplicative Update Method, Solving LPs
- Week 6: Pairwise independence, Finding distinct elements in a stream
- Week 7: Finding distinct elements in a stream, Chernoff Bounds
Book: Randomized Algorithms by Motwani and Raghavan
- Week 8: Streaming Algorithms : Frequency moments, count-min sketch, k-wise independence
Lecture Notes by Amit Chakrabarti
- Week 9: Dimensionality Reduction, Johnson Lindenstrauss Lemma
- Week 10: Online algorithms, competitive ratio, Ski Rental -- deterministic and online algorithms.
- Week 11: List Update Problem, Potential functions, Paging/Caching, 1-bit LRU
- Week 12: Load Balancing, VC Dimension
Lecture Notes by Sariel Har-Peled
- Minor: 20% each
- Assignments/Quizzes: 20%
- Major: 40%
You should take this course only if you are really interested in algorithms. No conversion to audit will be allowed.