| Lecture | Topics Covered | Resources |
|---|---|---|
| Lecture 1 | Medians and order statistics | |
| Lecture 2 | Dijkstra's Shortest Path Algorithm, Bellman Ford Algorithm, Correctness proofs, A min-heap 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, F-heaps and a bit more! |
| Lecture 5 | Review of F-heaps, Minimum Spanning Tree Generic Algorithm, Correctness Proof, Prim's Algorithm, Kruskal's Algorithm, Running Time Analysis, Union-Find 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 push-relabel 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 |