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.
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.
Flow Networks: Ford-Fulkerson, Edmonds Karp, Applications of maximum flows -
Efficient algorithms for maximum bipartite matching, minimum cost matching. NPCompleteness: Important NP-Complete Problems, Polynomial time reductions,
Approximation algorithms, Parallel Algorithms (overview): Tree Contraction - Divide
and Conquer - Maximal Independent Set. External-Memory Algorithms - Accounting
for the Cost of Accessing Data from Slow Memory – Sorting - B-trees - Cacheoblivious Algorithms for Matrix Multiplication and Binary Search.