CS60023 Approximation and Online Algorithms

Instructor:

 Swagato Sanyal

Teaching Assistant:

 Arnab Maiti

Course overview:

 This course is divided into the following two parts:
  1. Designing and analyzing polynomial time algorithms that approxiately solve NP-hard optimization problems,

  2. Designing and analyzing algorithms in the online computational model in which the input arrives piece by piece, and an irrevocable decision needs to be made whenever such a bit arrives without the knowledge about future bits.
  The course is of theoretical flavour and involves mathematically deriving bounds on performance of algorithms or establishing non-existence of algorithms. Have a look at the webpage of the last offering of this course to get a sense of the topics to be covered.

Pre–requisites:
  1. Mathematical maturity.

  2. Algorithms-II and Discrete Structures for UG students.
Besides, reasonable assumptions about the knowledge in various CSE basic core courses of the attendees will be freely made.

Classes:

 Venue: Microsoft Teams. Timings: Monday 5-6pm, Thurday 5-6pm, Friday 5-6pm.

Evaluation:

 2-3 long/short tests (approximately evenly spaced in the semester), 3-4 assignments, attendance+other class acitivities (teacher's assessment). Conduction of exams, dissemination and submission of assignments will happen in the CSE Moodle course.

References:
  1. V. Vazirani, Approximation Algorithms, Springer, 2003.

  2. D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge, 2011.

  3. A. Fiat and G. Woeginger, Online Algorithms, Lecture Notes in Computer Science, no. 1442, Springer, 1998 (Edited Volume).
Lectures:

Lectures Date Class notes Reference Reading