| Course Code: CS2002 Course Name: Design and Analysis of Algorithms Prerequisites: CS1213 Syllabus: Algorithm design techniques : the greedy method, divide-and-conquer, dynamic programming, backtracking, branch and bound, local search; Priority Queues : binomial heaps, Fibonacci heaps; Amortized analysis : techniques, some examples like Fibonacci heaps, Soft heap of Kaplan and Zwick, or the disjoint-set union-find data structure; Graph Algorithms : strong connectivity, biconnectivity, topological sort, minimum spanning trees, single pair shortest paths, all pair shortest paths, network flow; String matching algorithms; Introduction to a selection from the following topics : randomized algorithms, approximation algorithms, algebraic and number theoretic algorithms, parallel/distributed algorithms, parameterized algorithms; Complexity classes : P, NP, PSPACE; reducibility, NP-hard and NP-complete problems; Texts: 1. Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). MIT Press, 2009. 2. Kleinberg, Jon, and Eva Tardos. Algorithm Design. Addison-Wesley, 2006. References: 1. Aho, A. V., J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983. 2. Aho, A. V., J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Algorithms. Addison-Wesley, 1974. 3. Sahni, Sartaj. Data Structures, Algorithms and Applications in C++. McGraw-Hill, 2001. 4. Goodrich, Michael T., and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, 2001. |