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
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.
Understanding and Using Linear Programming by Jiří Matoušek and Bernd Gärtner
Parameterized Algorithms by Cygan et al.
Randomised Algorithm by Rajesh Motwani
July 21: Welcome
Aug 19 - 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 7: Pseudo-polynomial time algorithm from FPTAS, LP Duality
Chapter 8 & 12 of Ref [1]
Chapter 6 Ref [3]
18.08.2026
Lecture 8: LP Rounding and dual fitting: Set cover
Chapter 13 & 14 of Ref [1], Chapter 3 Ref [3]
19.08.2026
Lecture 9,10: Student Presentations: Multicut, multiway cut, k-center, shortest superstring
Chapter 4-8 of Ref [1]
20.08.2026
Lecture 11: Student Presentations: Bin packing, Min Makespan
Chapter 9,10 of Ref [1]
25.08.2026
Lecture 12: Primal Dual Schema, set cover algorithm,
Student Presentation: Euclidean TSP
Chapter 15 of Ref [1]
27.08.2026
Lecture 13: Parameterized Algorithm, Branching: Vertex Cover, FVS
Chapter 3 Ref [4]