**COL758: Advanced Algorithms**

**Week 1**: Matroids, greedy algorithm.

**References:**

**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:**

**Week 6:**Pairwise independence, Finding distinct elements in a stream

**References:**

**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:**

**Week 10:**Online algorithms, competitive ratio, Ski Rental -- deterministic and online algorithms.

**References:**

**Week 11:**List Update Problem, Potential functions, Paging/Caching, 1-bit LRU

**Week 12:**Load Balancing, VC Dimension

**References:**

**References:**

Lecture Notes by Sariel Har-Peled

- Minor: 20% each
- Assignments/Quizzes: 20%
- Major: 40%
- Assignment 1 (Due date: Jan 31 midnight, sumbit using moodle or email gzip file to TA)

data.csv data.mat

Solutions to Assignment 1

You should take this course only if you are really interested in algorithms. No conversion to audit will be allowed.