Algorithms (II Sem-26)

Instructors: Kavitha Telikepalli and Nikhil Kumar

Classes: 11:30 AM–1:00 PM on Tuesday and Thursday in A-201

Evaluation: Two exams worth 25% each, assignments and in-class quizzes worth 30% in total, and end-of-course presentations worth 20%.

Topics Covered

Lecture 1 (18.08, K): Course Outline, Deterministic Median Finding in Linear Time (Ch-9, [CLRS])
Lecture 2 (20.08, K): Discrete Fast Fourier Transform (Ch-12, [CLRS])
Lecture 3 (25.08, K): Karger's Minimum Cut Algorithm (Ch-1.1, [MR])
Lecture 4 (27.08, K): Karger–Stein Algorithm (Ch-10.2, [MR]), Introduction to s–t Flows and Cuts
Lecture 5 (01.09, N): Max-Flow Min-Cut Theorem, Ford–Fulkerson Algorithm, Flow Decomposition (Ch-7,[KT])
Lecture 6 (03.09, N): Edmonds–Karp Algorithm: Shortest and Fattest Augmenting Paths (Ch-7, [KT])
Lecture 7 (08.09, N): Applications of Max-Flow: Minimum Cuts, Bipartite Matching, and Gomory–Hu Trees
Lecture 8 (10.09, K): Goldberg–Tarjan Push–Relabel Maximum Flow Algorithm; notes by Kurt Mehlhorn
Lecture 9 (15.09, K): Push–Relabel Algorithm Contd.; notes by Kurt Mehlhorn
Lecture 10 (17.09, K): Dijkstra's Algorithm for Single Source Shortest Path; Fibonacci Heap
Lecture 11 (22.09, K): Fibonacci Heap Contd.; Quiz 1

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein [CLRS].
Algorithm Design by Jon Kleinberg and Éva Tardos [KT].
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan [MR].
Approximation Algorithms by Vijay V. Vazirani [VV].