2K6 CS 805(A) ADVANCED TOPICS IN ALGORITHMS

Module I (12 hours)
Balanced binary search trees – AVL Trees – Height of an AVL Tree, Insertion Procedure, Deletion Procedure. Red Black Trees – Properties of Red Black Trees, Rotations, Insertion and Deletion procedures. B-Trees- Definition, Basic operations on B-Tree, Deleting a key from B-Tree. Binomial Heaps- Binomial Trees and Binomial Heaps, Operations on Binomial Heaps. Fibonacci Heaps- Structure of Fibonacci Heaps, Mergeable Heap operations, Decreasing a key and Deleting a node, Bounding the maximum degree.
Module II (12 hours)
Flow Networks – Properties of Flow Networks, Ford-Fulkerson method, Edmonds-Karp method, Maximum Bipartite Matching, Push Relabel algorithm, The Relabel to Font Algorithm. Solving Systems of Linear Equations – Overview of LUP decomposition, Forward and Back Substitution, Computing an LU Decomposition, Computing LUP decomposition.
Module III (14 hours)
Linear Programming – Overview of Linear Programming, Standard and Slack forms, Converting linear programs into slack forms, The Simplex Algorithm, Initial basic feasible solution, Fundamental theorem of Linear Programming. Polynomials and FFT – Representation of Polynomials, DFT and FFT, divide and conquer FFT algorithm, efficient parallel FFT algorithm.
Module IV (12 hours)
Pattern Matching Algorithms – Finite Automata based Pattern Matching, Rabin Karp method, The Boyer Moore heuristic, Longest Common Subsequence. Computational Geometry – Line Segment Properties, Segments intersection problem, Finding Convex Hull, Graham Scan method, Jarvis’s March, Finding Closest pair of points.

Reference books
1 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Prentice Hall of India
2. Basse S., Computer Algorithms – Introduction to Design and Analysis, Addison Wesley
3. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer verlag N.Y, 1992