CS512 | DESIGN AND ANALYSIS OF ALGORITHMS | 3-0-0-6 |
Pre-requisites : Nil |
Syllabus : Models of Computation: space and time complexity measures, lower and upper bounds; Design techniques: greedy method, divide-and-conquer, dynamic programming; Amortized analysis: basic techniques, analysis of Fibonacci heap and disjoint-set forest; Graph algorithms: connectivity, topological sort, minimum spanning trees, shortest paths, network flow; String matching; Average-case analysis; NP-completeness. |
Texts : 1. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C., Introduction to Algorithms, MIT Press, 2009.
2. Kleinberg, J. and Tardos, E., Algorithm Design, Addison Wesley, 2006. |
References : 1. Dasgupta, S., Papadimitriou, C. and Vazirani, U., Algorithms, McGraw-Hill, 2007.
2. Aho, A., Hopcroft, J. E. and Ullman, J.D., The Design and Analysis of Computer Algorithms, Pearson, 2002. |