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)