CS 345: Algorithms II

Units: 3-0-0-9

Pre-requisites: ESC101, CS210

Course Contents:

1. Amortized analysis.
2. Exposure to some advanced data structures (For example, Fibonacci heaps or augmented data structures or interval trees or dynamic trees).
3. As part of CS210/ESO211 course, three algorithm paradigms, namely, greedy method, divide and conquer, and dynamic programming are discussed. These algorithm paradigms should be revisited in CS345, but with advanced applications and/or emphasis on their theoretical foundations as follows.

1. Greedy method: theoretical foundations of greedy method (matroids) and other applications.
2. Divide and Conquer: FFT algorithm and other applications.
3. Dynamic Programming: Bellman Ford algorithm and other applications.

4. Graph algorithms: all-pairs shortest paths, biconnected components in undirected graphs, strongly connected components in directed graphs, and other problems.
5. Pattern matching algorithms.
6. Lower bound on sorting.
7. Algorithms for maximum flow and applications.
8. Notion of intractability: NP-completeness, reduction (the proof of Cook-Levin theorem may be skipped)
9. Exposure to some (one or more) topics from the following list :

1. Approximation algorithms.
2. Algebraic and number theoretic algorithms.
3. Computational Geometry.
4. Linear programming.
5. Parallel/distributed algorithms.
6. Randomized algorithms.

Books and References:

1. J Kleinberg, E Tardos, Algorithm Design, Addison-Wesley, 2005.
2. TH Cormen, CF Leiserson, RL Rivest, C Stein, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.
3. AV Aho, J Hopcroft, JD Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974.