MA 252

DESIGN AND ANALYSIS OF ALGORITHMS

3-0-0-6

Prerequisites:  MA251 or equivalent

Syllabus:

Sorting and order statistics – linear time sorting, randomize quicksort, lower bounds for sorting, median and order statistics, randomized selection; Design and analysis techniques – greedy method, divide-and-conquer, dynamic programming, amortized analysis; Graph algorithms – properties of BFS and DFS, connected components, topological sort, minimum spanning trees, shortest paths, maximum flow; NP-completeness; Approximation algorithms.

Textbooks:

1.     T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Prentice-Hall of India, 2009.

References:

1.     A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Pearson Education, 2006.

2.     J. Kleinberg and E. Tardos, Algorithm Design, Pearson Education, 2006.

3.     E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Galgotia Publishers, 1984.

4.     M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley, 2001.

5.     H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall of India, 1992.