CS 345: Algorithms II
Pre-requisites: ESC101, CS210
- Amortized analysis.
- Exposure to some advanced data structures (For example, Fibonacci heaps or augmented data structures or interval trees or dynamic trees).
- 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.
- Greedy method: theoretical foundations of greedy method (matroids) and other applications.
- Divide and Conquer: FFT algorithm and other applications.
- Dynamic Programming: Bellman Ford algorithm and other applications.
- Graph algorithms: all-pairs shortest paths, biconnected components in undirected graphs, strongly connected components in directed graphs, and other problems.
- Pattern matching algorithms.
- Lower bound on sorting.
- Algorithms for maximum flow and applications.
- Notion of intractability: NP-completeness, reduction (the proof of Cook-Levin theorem may be skipped)
- Exposure to some (one or more) topics from the following list :
- Approximation algorithms.
- Algebraic and number theoretic algorithms.
- Computational Geometry.
- Linear programming.
- Parallel/distributed algorithms.
- Randomized algorithms.
Books and References:
- J Kleinberg, E Tardos, Algorithm Design, Addison-Wesley, 2005.
- TH Cormen, CF Leiserson, RL Rivest, C Stein, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.
- AV Aho, J Hopcroft, JD Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974.