MTL760: Advanced Algorithms

Spring semester, 2021-22

---

Lectures by:
Prof. Minati De and Ashutosh Rai.

Time of the class:
Mondays and Thursdays 8:00am to 9:20am.

Office hours:
by email appointment.

Syllabus:
The course will be divided into two parts, and will roughly cover the following topics.

Part 1 (taught by Prof. Minati De): Randomized algorithms and Probablistic Analysis.

Part 2 (taught by Ashutosh Rai): NP-completeness and ways to deal with it, including approximation algorithms and parameterized algorithms.


Course Material:
We will be referring to materials from the following books. The exact references would be told during the lectures.
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
Probability and Computing by Michael Mitzenmacher and Eli Upfal
Algorithm Design by Jon Kleinberg and Eva Tardos
Approximation Algorithms by Vijay V. Vazirani
Parameterized Algorithms by Marek Cygan, Fedor Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh

Credits:
The course will be evaluated on a 100 point scale.
Students will be asked to make lecture notes, which will be worth 20 points.
The minor and major will be worth 40 points each.
To pass or audit pass the course (i.e., to get a D grade), you need to have at least 30 points.

---