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.