CS210

ADVANCED ALGORITHMS

Objectives

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

 

Outcomes

  • 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

 

TEXT BOOKS

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