Lecture  Topics Covered  Resources 

Lecture 1  Medians and order statistics  
Lecture 2  Dijkstra's Shortest Path Algorithm, Bellman Ford Algorithm, Correctness proofs, A minheap implementation of Dijkstra's algorithm and its complexity analysis 

Lecture 3  Solving systems of Difference Constraints using Bellman Ford Algorithm ; Idea of Amortization 

Lecture 4  Fibonacci Heap Implementation of Dijkstra's Algorithm 
Ramesh Hariharan's lecture
slides on amortization, Fheaps and a bit more! 
Lecture 5  Review of Fheaps, Minimum Spanning Tree Generic Algorithm, Correctness Proof, Prim's Algorithm, Kruskal's Algorithm, Running Time Analysis, UnionFind Data Structure Problem 

Lecture 6  Review of Disjoint Set Data Structure Problem, Union by Rank with Path Compression 
Assignment 1 due on 27/09/11 
Lecture 7  Time Complexity of Kruskal's Algorithm with Union by Rank and Path Compression Maximum Flow Problem, Ford Fulkerson Algorithm 
Some Notes on Union Find 
Lecture 8  Correctness of Ford Fulkerson, Max Flow Min Cut Theorem Maximum Bipartite Matching using Ford Fulkerson, Proof of Hall's Theorem using Max Flow Min Cut Theorem 
Kurt Mehlhorn's comprehensive slides on Max Flow Problem 
Lecture 9  Dinic's Algorithm, Correctness and Complexity Issues  
Lecture 10  Idea of Preflow, Generic Push Relabel Algorithm, Termination and Correctness 
Assignment 2 due on 19/10/11 [Refer this paper by Uri Zwick for solving Problem 1 ] 
Lecture 11  Bounding the running time of pushrelabel algorithm at O(n^3); Polynomial Multiplication; Naive Method Complexity 

Lecture 12  Polynomial Multiplication in O(n log n) using FFT;  Ramesh Hariharan's lecture
slides on polynomial computation 
Lecture 13  String Matching Problem ; Solution by constructing an automaton ; KMP Algorithm 
Assignment 3 due on 10/11/11 
Lecture 14  Randomised Algorithms  Introduction; Randomised Quicksort; Incremental deterministic algorithm for two dimensional LP problem 

Lecture 15  Randomised Algorithm for 2D LP; Convex Hull Problem; Deterministic Incremental Algorithm for Convex Hull 

Lecture 16  Randomised Algorithm for Convex Hull; Monte Carlo Algorithms  Definition; Primality Testing Problem; Fermat's Primality Testing 
Assignments  20 marks 
Final Exam  50 marks 
Presentation  30 marks 