Advanced Data Structures and Algorithms

Code: MA654 | L-T-P-C: 3-0-0-6

MA 512: Data Structures and Algorithms or MA 252:Design and Analysis of Algorithms or Equivalent Course

Review of design techniques: greedy method, divide-and-conquer, dynamic programming with advanced applications and/or emphasis on their theoretical foundations; Review of amortized analysis; Data structure: B-trees, Fibonacci heaps with application to Prim's MST algorithm, interval trees, data structures for disjoint sets; Algorithms for maximum flow and its applications; String matching; Approximation Algorithms: Set cover, max-SAT, knapsack, bin packing, scheduling, traveling salesman tour; Introduction to Randomized Algorithms; Geometric Algorithms: convex hull algorithms, and its lower bound, line segment intersection, closest pair points.

Texts:

1. J Kleinberg and E Tardos, Algorithm Design, Addison-Wesley, 2005.
2. TH Cormen, CF Leiserson, RL Rivest, and C Stein, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.

References:

1. AV Aho, J Hopcroft, and JD Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974.