Algorithms - Monsoon 2011

Instructor : Dr. T. Kavitha

Venue : A-212

Timings : 2 p.m. - 3.30 p.m. on Tuesdays and Thursdays

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

Evaluation Policy :-

Assignments 20 marks
Final Exam 50 marks
Presentation 30 marks

Textbooks:-

1. Introduction to Algorithms - CLRS