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 (30%), Midterm (20%) , 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 Algorithms by Rajesh Motwani and Prabhakar Raghavan
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
July 21: Welcome
Aug 19 - 20: Student presentations on Approximation Algorithms
Sept 7: Mid term
Oct 7: Assignment 1 Due
Oct 26: Assignment 2 Due
Nov 5: Quiz on Topics covered in Lectures 13 - 25
Nov 14: Final term
Approximation Algorithms: Combinatorial and LP based, Lower bounds
Parameterized Algorithms: Branching, Kernelization, Iterative Compression, color-coding, inclusion-exclusion, Lower Bounds
Randomised Algorithms, One-sided errors, Probabilistic Methods, Derandomization techniques
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
Chapter 3 of Ref [4]
01.09.2026
Lecture 14: Branching: FVS, Vertex Cover above LP
Chapter 3 of Ref [4]
03.09.2026
Lecture 15:Branching: Vertex Cover with Above guarantee parameter
Chapter 3 of Ref [4]
15.09.2026
Lecture 16: Kernelization: Vertex cover, feedback vertex set
Chapter 2 of Ref [4]
17.09.2026
Lecture 17: Crown decomposition: VC, Max 2-SAT
Chapter 2 of Ref [4]
22.09.2026
Lecture 18: Kernelization: Hitting Set, Set packing: Sunflower lemma
Chapter 2 of Ref [4]
24.09.2026
Lecture 19: Iterative Compression, Disjoint Set Problem: VC, FVS
Chapter 4 of Ref [4]
29.09.2026
Lecture 20: Color coding: k-path, random separation: subgraph isomorphism
Chapter 5 of Ref [4]
01.10.2026
Lecture 21: Longest cycle, Inclusion-exclusion: k-path in poly space
Chapter 5, Chapter 10.1 of Ref [4]
06.10.2026
Lecture 22: W-hardness definitions, prameterized reductions
Chapter 13 of Ref [4]
13.10.2026
Lecture 23: Randomized Algorithms: Verifying Matrix Multiplication, Min Cut, Complexity classes
Chapter 1.3- 1.4 of Ref [6]
Chapter 1.1, 1.2, 1.5 of Ref [6]
14.10.2026
Lecture 24: Randomized Quick Sort & Average Case Analysis, Coupon Collector's problem
Chapter 2.4-2.5, 3.3 of Ref [6]
Chapter 3.2, 3.6 of Ref [5]
27.10.2026
Lecture 25: Coupon Collector's problem, Union Bound, Average case analysis of Stable Matching algorithm
Chapter 2.4-2.5, 3.3 of Ref [6]
Chapter 3.2, 3.6 of Ref [5]
29.10.2026
Lecture 26: Probabilistic Methods: Basic Counting, Expectation Argument, Derandomization Using Conditional Expectations, Sample and Modify
Chapter 6 of Ref [6]
3.11.2026
Lecture 27: Lovász Local Lemma
Chapter 6 of Ref [6]