Pre-requisites : CS201 plus CS202 or equivalent
Models of Computation: space and time complexity measures, lower and upper bounds Design techniques: the greedy method, divide-and-conquer, dynamic programming,backtracking, branch and bound Lower bound for sorting Selection Graph Algorithms: connectivity, strong connectivity, biconnectivity, topological sort, shortest paths, minimum spanning trees, network flow The disjoint set union problem String matching NP-completeness Introduction to approximate algorithms and Randomized algorithms.
1.T H Cormen, C E Leiserson, R L Rivest and C Stein, Introduction to Algorithms, MIT Press, 2001.
2.J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.
1. A Aho, J E Hopcroft and J D Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
2. S Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 2001.
3. M T Goodrich and R Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons, 2001.