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

Homeworks

Major Exam

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

References