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: 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


Practice Problems:
  1. Practice problem set on amortized analysis
  2. Practice problem set on Fibonacci heap
  3. Practice problem set on maximum flow
  4. Practice problem set on applications of maximum flow


References:
  1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
  2. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
  3. Jeff Erickson, Algorithms, 2019.
  4. Vijay V Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
  5. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry, Springer, 2008.
  6. 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.
  7. Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms
  8. Eli Upfal and Michael Mitzenmacher, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis