Course

Unit 1

Algorithm Analysis- Methodologies for Analyzing Algorithms, Asymptotic growth rates, Amortized Analysis. Number Theory: Preliminaries, FLT, Euclid’s algorithm (extended). Totient function, Sieve for primes, Inverse modulo n, Modular exponentiation, Applications of graph algorithms: Topological sort, Strongly Connected Components, Bi-connected Components, Bridges, Articulation points. All Pair Shortest Paths, Single Source Shortest Paths. Computational Geometry: Convex Hull, closest pair of points in 2D, the triangle with smallest perimeter in 2D, Determining whether a set of line segments have one or more intersections.

Unit 2

Applications of Divide-and-Conquer, Greedy techniques and Dynamic Programming – Knapsack, Median finding, Scheduling algorithms, Party planning, bitonic TSP etc., String matching algorithms: KMP, Rabin Karp, Aho-Corasick, 2D queries, efficient algorithms for longest palindrome, Longest Common Substring.

Unit 3

• Cormen T. H., Leiserson C. E., Rivest R. L. and Stein C., “Introduction to Algorithms”, Prentice Hall of India Private Limited, Third Edition, 2009
• Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms”, Cambridge University Press, 1995.
• Vijay V. Vazirani., “Approximation Algorithm”, Springer, 2003