| Course Code: CS207 Course Name: Design and Analysis of Algorithms Prerequisites: CS203 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. T. H. Cormen, C. F. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, Prentice Hall of India, 2009. 2. J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005. References: 1. A. V. Aho, J. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison- Wesley, 1983. 2. A. V. Aho, J. Hopcroft, J. D. Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974. 3. S. Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 2001. 4. M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons, 2001. |