Homepage of Kavitha Telikepalli Details of lectures
Lecture 1 (Jan 8): Introduction to the max flow problem, min cost flow problem
Lecture 2 (Jan 10): Ford-Fulkerson algorithm
Lecture 3 (Jan 15): Max flow-min cut theorem, Maximum matching in bipartite graphs, proof of Hall's theorem
Lecture 4 (Jan 17): Dinic's algorithm using layered networks
Assignment Sheet 1
Lecture 5 (Jan 22): Analysis of Dinic's algorithm
Lecture 6 (Jan 24): Preflow-Push algorithm
Lecture 7 (Jan 29): Analysis of Preflow-Push algorithm, Randomized Quicksort
Lecture 8 (Jan 31): Randomized Min-Cut algorithm
Assignment Sheet 2
Lecture 9 (Feb 5): Faster Randomized Min-Cut algorithm
Lecture 10 (Feb 7): Analysis of the min-cut algorithm, randomized 2-D Linear Programming
Lecture 11 (Feb 12): Analysis of randomized 2-D Linear Programming, Randomized primality testing
Lecture 12 (Feb 14): Analysis of Miller-Rabin primality testing algorithm
Lecture 13 (Feb 19): Randomized primality testing, Polynomials and the FFT
First Mid-Term Test (on Feb 21)
Lecture 14 (Feb 26): Polynomials and the FFT, String Matching algorithms
Lecture 15 (Feb 28): Rabin-Karp algorithm, String matching with finite automaton, Knuth-Morris-Pratt algorithm
Lecture 16 (Mar 5): Analysis of the KMP algorithm, Shortest Path Algorithms: Bellman-Ford
Assignment Sheet 3
Lecture 17 (Mar 7): Solving systems of difference constraints, Dijkstra's algorithm
Lecture 18 (Mar 12): Fibonacci Heaps
Lecture 19 (Mar 14): Fibonacci Heaps (contd.), Prim's algorithm
Lecture 20 (Mar 21): Kruskal's algorithm, Union-Find data structure
Assignment Sheet 4
Second Mid-Term Test (on Mar 26)
Lecture 21 (Mar 28): Analysis of Union-Find data structure
Lecture 22 (Apr 2): Dynamic programming, Introduction to the class NP
Lecture 23 (Apr 4): SAT and examples of other NP-complete problems
Lecture 24 (Apr 9): More NP-complete problems and pseudopolynomial time algorithm for the knapsack problem
Assignment Sheet 5
Lecture 25 (Apr 11): Totally unimodular matrices, Introduction to approximation algorithms
Assignment Sheet 6
Final Exam (on Apr 24)