CS31005 Algorithms II - Spring 2025

Instructor: Sudeshna Kolay and Palash Dey

Teaching Assistants: Swapnil Ghosh, Ashlesha Hota, Saideep Pandey, Abhishek Shaw, Dip Rajeshbhai Shambhvani

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: NC442 (for odd roll numbers) and NC443 (for even roll numbers)
Timings: Thursday 3-4:55, Friday 2-3:55 [slot V4].

Grading: Class test: 20%, Mid-term: 30%, Final: 50%

Announcements: Lectures:
Week 1 Jul 25 Amortized Analysis Reference: CLRS book
Jul 26 Institute Class Suspension
Week 2 Jul 31 Dynamic Table,
Fibonacci Heap		 Reference: CLRS, KT books,
and this
Aug 1
Week 3 Aug 8 Network Flow
Ford Fulkerson Method

Tutorial on amortization
and Fibonacci heap

Reference: CLRS, KT, JE books

Prof. Tim Roughgarden's Lecture Notes:
this, this, this, this
Aug 9
Week 4 Aug 14 Edmond-Karp Algorithm
Dinic's Algorithm
Aug 15 Institute Holiday
Week 5 Aug 21 Push-relabel Algorithm Reference: CLRS, KT, JE books

Prof. Tim Roughgarden's Lecture Notes:
this, this, this, this
Aug 22

Tutorial on maximum flow
Week 6 Aug 28 Push-relabel Algorithm
Application of Max-flow:
Bipartite Matching, Hall's Theorem,
Konig's Theorem.

 Reference: CLRS, KT, JE books
Notes on Hall's Theorem and Konig's Theorem
Aug 29
Week 7 Sep 4 Edmond's Blossom Algorithm Reference: this
Sep 5 Institute Holiday
Week 8 Sep 11

Tutorial on applications of maximum flow
Sep 12 Doubt-clearing session


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 push relabel algorithm
  5. Practice problem set on applications of 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