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