Course

Algorithm Analysis: Asymptotic Notation-Standard – Recurrences – Solution to Recurrences Divide and Conquer – Sorting, Matrix Multiplication and Binary Search. Dynamic Programming- Longest common substring/subsequence – Matrix Chain Multiplication – 0-1 Knapsack problem – Coin Change problem. Greedy algorithms: Fractional knapsack, job scheduling, matroids. Graph Algorithms – Graph Traversal, Single- Source Shortest Paths, All pairs Shortest Paths, Depth First Search, Breadth First Search and their applications, Minimum Spanning Trees. Network Flow and Matching: Flow Algorithms – Maximum Flow – Cuts – Maximum Bipartite Matching – Graph partitioning via multi-commodity flow,Karger’r Min Cut Algorithm. Amortized Analysis – Aggregate Method – Accounting Method – Potential Method. String Matching Algorithms: KMP, Aho- Korasik algorithm, Z-algorithm. NP Completeness: Overview – Class P – Class NP – NP Hardness – NP Completeness – Cook Levine Theorem – Important NP Complete Problems – Reduction of standard NP Complete Problems (SAT, 3SAT, Clique, Vertex Cover, Set Cover, Hamiltonian Cycle). Approximation Algorithms: Approximation algorithms for known NP hard problems – Inapproximability – Analysis of Approximation Algorithms.