| Course Code: CS512 Course Name: Design and Analysis of Algorithms Prerequisites: 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. |