Instructor: Sanjukta Roy
Lecture timing: Tuesday and Thursday 11:10 - 12:50
Location: room# 705
Evaluation: Your grade will be based on your performance in quizzes (20%), Midterm (30%) , and final exam (50%).
Basic understanding of algorithms is required.
Practice problem sets for basics of Algorithms
Following are some basic books for algorithms:
Algorithm Design by John Kleinberg and Éva Tardos
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
Approximation Algorithms by Vijay V. Vazirani
Parameterized Algorithms by Cygan et al.
Randomised Algorithm by Rajesh Motwani
July 21: Welcome
Aug 18 - 20: Student presentations on Approximation Algorithms
Approximation Algorithms: Combinatorial and LP based, Lower bounds
Parameterized Algorithms: Branching, Kernelization, Iterative Compression, DP over subsets, Lower Bounds
Randomised Algorithms
Date
Topics Covered
References
21.07.2026
Lecture 1: Introduction to the course, some basics of Algorithms, NP hardness
Chapter 8 of Pre-requisit Reference 1
28.07.2026
Lecture 2: Vertex Cover and Maximal Matching, Greedy Algorithms: Set Cover
Chapter 1 of Ref [1]
30.07.2026
Lecture 3: Set Cover, Steiner tree
Chapter 2 & 3 of Ref [1]
04.08.2026
Lecture 4: Metric Steiner tree, TSP Gap reduction
Chapter 3 of Ref [1]
06.08.2026
Lecture 5: Metric TSP
Chapter 3 of Ref [1]
11.08.2026
Lecture 6: Knapsack problem, Pseudopolynomial algorithm, Strong NPH, PTAS, FTPAS for Knapsack
Chapter 8 of Ref [1]
13.08.2026
Lecture 5: Pseudo-polynomial time algorithm from FPTAS, LP Duality
Chapter 8 & 9 of Ref [1]