CS31005 Algorithms II

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:

First class will be on July 24.
First class test will be on August 21 from 6 PM in CSE department. Seating plan is here.
Mid-semester question paper: here.
Second class test will be on October 24 from 6 PM in CSE department. Seating plan is here.

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
Week 9	Oct 9	Stable Matching Randomized Selection with Analysis	Reference: this and this
	Oct 10
Week 10	Oct 16	O(1) Time Selecttion Sorting Lower Bound KMP String Matching Algorithm Karger's Algorithm for Min-Cut	Reference: CLRS book and this
	Oct 17
Week 11	Oct 23	Tutorial on Stable Marriage, Order Statistics, and String Matching Doubt Clearing Session
	Oct 24	Karger Stein Algorithm	Reference: this

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 flow
Practice problem set on stable matching
Practice problem set on order statistics and string matching

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