'Advanced Algorithms and Analysis' is a Soft Core course offered for the M. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.
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
TEXTBOOKS/REFERENCES
Course Outcome | Bloom’s Taxonomy Level | |
CO 1 | Understand the key techniques and theory behind the type of random variable and distribution | L2 |
CO 2 | Use effectively the various algorithms for applications involving probability and statistics in computing (data analytics) | L3 |
CO 3 | Evaluate and Perform hypothesis testing and to conclude | L4, L5 |
CO 4 | Design and build solutions for a real world problem by applying relevant distributions | L4, L5 |