Design and Analysis of Algorithms

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

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.

Texts:

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

 

References:

• A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Pearson Education, 2006.
• J. Kleinberg and E. Tardos, Algorithm Design, Pearson Education, 2006.
• E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Galgotia Publishers, 1984.
• M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley, 2001.
• H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall of India, 1992.