CS31005 Algorithms II

CS31005 Algorithms II - Autumn 2026

Instructor: Abhranil Chatterjee and Palash Dey

Teaching Assistants: Jada Venkata Yaswanth, Devanshu Agrawal, Mundada Ayush, Parth Shashin Patil, and Somak Poddar

Course overview:
This is a second level algorithms course. Tentative topics: amortized analysis, Fibonacci heap, network flow, matching, NP-completeness, approximation algorithms, randomized algorithms, and parameterized algorithms

Classes:
Venue: NC231 (for odd roll numbers) and NC232 (for even roll numbers)
Timings: Thursday 3-4:55, Friday 2-3:55 [slot V4].

Grading: Attendance: 10%, Class test: 30%, Mid-term: 30%, Final: 30%

Announcements:

First class will be on July 23, 2026.
First class test will be on August 19 from 6 PM in CSE department. Seating plan is here.
Second class test will be on October 28 from 6 PM in CSE department. Seating plan is here.

Lectures:

Week 1	Amortized Analysis	Reference: CLRS book
Week 2	Fibonacci Heap Introduction to Maximum Flow	Reference: KT, JE books CLRS book (3rd Edition)
Week 3	Network Flow Ford Fulkerson Method Edmond-Karp Algorithm Tutorial on amortization and Fibonacci heap	Reference: CLRS, KT, JE books Prof. Tim Roughgarden's Lecture Notes: this, this, this, this Notes on Hall's Theorem and Konig's Theorem
Week 4	Dinic's Algorithm Push-Relabel Algorithm Tutorial on Ford Fulkerson and Edmond-Karp Algorithms
Week 5	Push-Relabel Algorithm Applications of Max-Flow: Hall's Theorem, Konig's Theorem
Week 6	Maximum Matching in General Graphs: Edmond's Blossom Algorithm Tutte-Berge Theorem Tutorial on Applications of Max Flow	Reference: Notes
Week 7	Stable Matching Institute Holiday	Reference: Notes
Week 8	Order Statistics Sorting Lower Bound Tutorial on Blossom Algorithm and Stable Matching	Reference: CLRS Book
Week 9	String Matching: KMP Algorithm Tutorial on Order Statistics, Sorting Lower Bound, and String Matching	Reference: CLRS Book
Mid-Semester Exam Break
Week 10	Karger's Min-Cut Algorithm Karger-Stein Min-Cut Algorithm Introduction to Complexity Classes: P, NP, co-NP Polynomial Time Many-to-One Reduction Self Reduction of SAT	Notes, CLRS and KT Books

Practice Problems:

Practice problem set on amortized analysis
Practice problem set on Fibonacci heap
Practice problem set on maximum flow
Practice problem set on push relabel algorithm
Practice problem set on applications of maximum flow
Practice problem set on stable matching
Practice problem set on order statistics and string matching
Practice problem set on Karger's min-Cut algorithm, introduction to complexity classes

References:

Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
Jeff Erickson, Algorithms, 2019.
Vijay V Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry, Springer, 2008.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms. You can download from here.
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms
Eli Upfal and Michael Mitzenmacher, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis