Special Topics in Algorithms - Online Computation


Course code

   

COL866

Instructor

   

Ashish Chiplunkar (ashishc@...)

Classes

   

LH 612 SIT 006, Monday and Thursday 14:00 - 15:30 (Slot AA)

Office hour

   

Bharti 409, Monday and Thursday 15:30 - 16:00



Recorded Lectures

Recorded Lecture 1
Recorded Lecture 2
Recorded Lecture 3
Recorded Lecture 4
Recorded Lecture 5
Recorded Lecture 6
Recorded Lecture 7
Recorded Lecture 8
Recorded Lecture 9

Homeworks

Homework 1
Homework 2
Homework 3

Prerequisites

Discrete structures, algorithm design, probability and random variables. Students not satisfying these prerequisites are welcome to attend, but should meet the instructor before they commit to taking this course. Check this prerequisite test.


Motivation

Several computational problems require algorithms that have to commit to decisions in face of a restricted view of their input. A typical scenario is where the input is revealed over time, and the algorithm has to process each piece of input before it sees the next one. Such algorithms are called online algorithms. Caching is a canonical example of an online problem where on each cache miss, the algorithm (e.g. LRU, FIFO, etc.) has to decide which of the cached pages to evict to load the requested page. Naturally, online algorithms do not generally produce optimal solutions, but can they get close to an optimal algorithm which can see the entire input (a.k.a. offline algorithm)? How do we quantify this closeness? How do we prove bounds on how close-to-optimum an online algorithm can be? The course will involve techniques for designing and analyzing online algorithms and for proving impossibility results for several classical problems.


Content (tentative)

Definitions of online computation and competitiveness, rent-or-buy, caching, the potential method, impossibility results, randomized algorithms, Yao's principle, adversary hierarchy, k-server, work function algorithm, memoryless algorithms, online primal-dual, matchings, hiring secretaries, prophet inequalities, prophet secretary, contention resolution schemes.


Grading

For students opting for the AGP: 40% major, 20% minor 1, 10% best 2 of 3 surprise quizzes, 10% each of 3 homeworks 20% each minor, 20% easy short surprise quizzes, 0% homeworks.
For all other students: TBD.
Grading will be relative, that is, upper and lower cutoffs for grades will be decided considering the overall performance of the class. Lower cutoff for getting audit will be same as that for passing the course. Students may refer to only their own handwritten notes during the exams.

References

"Online Computation and Competitive Analysis" by Borodin and El-Yaniv + papers