DESIGN AND ANALYSIS OF ALGORITHMS

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

Prerequisites: MA 221, CS 201

Models of Computation: Turing machines and random access machines, space and time complexity measures, lower and upper bounds; Design and analysis techniques: the greedy method, divide-and-conquer, dynamic programming, backtracking, branch and bound. Priority Queues: heaps, binomial heaps, Fibonacci heaps. Sorting and order statistics: sorting algorithms (insertion-sort, bubble-sort, shell-sort, quick-sort, merge-sort, heap-sort and external-sort) and their analyses, selection. Graph Algorithms: connectivity, bi-connectivity, topological sort, shortest paths, minimum spanning trees, maximum flow. Advanced topics: the disjoint set union problem; NP-completeness; geometric, approximation, parallel, and randomized algorithms.

Texts:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, 2001.

References:

1. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
2. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Galgotia Publishers, 1984.
3. M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley, 2001.
4. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall of India, 1992.