Basic Information

This course is about elegant algorithms and data structures, many of which have been designed possibly several decades ago, however they continue to influence problems arising even today. The course is divided into three broad themes:

Flows and Cuts in Graphs Max Flow problem, Max-Flow Min-Cut Theorem, Ford Fulkerson, Dinitz Algorithm, Push Relabel Algorithm. Randomized Min Cut, Kargers Algorithm, Fast MinCut.

Matchings in Graphs Bipartite Matchings, Hopcroft Karp Algorithm, Weighted Bipartite Matching, Dulmage Mehndelson Decomposition, Edmonds Algorithm for non-bipartite Matching, Gallai Edmonds Decomposition. Stable Matchings.

Data Structures and Algorithms for Dynamic Graph problems Euler Tour Trees, Link Cut trees, Dynamic Connectivity, Dynamic Shortest Paths.

Course Grading:
MidSem + EndSem = 35+35 = 70%
4 Assignments = 4 * 5 = 20%
2 Tutorials = 2 * 5 = 20%