• To expose the students to advanced topics in algorithms including use of advanced concepts in data structures and algorithms for manipulations



  • Ability to apply hashing techniques, use data structures in new algorithms
  • Ability to comprehend complex real world scenarios and map to advanced algorithms understand


Unit – I

          Review of algorithmic paradigms, Finding max and min in a list adversary arguments selection in expected liner time, selection in worst case, hashing technique- hash tables, hash functions, open hashing, perfect hashing, related theorems.


Unit – II

         Binary search trees, AVL trees, randomly built binary search trees, optimal binary search trees, greedy strategy and matroids, weighted matroids and task scheduling problem, introduction to amortised analysis, illustrative examples


Unit – III

           B-Trees, Binomial heaps, data structures for disjoint sets, shortest paths: difference constraints and shortest paths, proofs of shortest path properties, relationship to matrix multiplication, Floyd-Warshall algorithm, Johnson’s algorithm for sparse graphs


Unit – IV

            Flow networks and their properties, Ford-Fulkerson method, maximum bipartite matching, FFT algorithm, DFT and FFT, efficient FFT implementation, primality testing basics, Miller-Rabin algorithm and its proof


Unit – V

           Polynomial time and exponential time algorithms, 3-CNF satisfiability and other representative hard problems, decision and optimization problems, encodings, formal language framework, verification algorithms, classes P and NP, NP-Hard and NP complete problems, efficient reduction proofs via examples



  • T. Cormen, C. Lieserson, R. Rivest, and C. Stein, “Introductions to Algorithms”, Prentice-Hall/India, 3rd edition, 2009