'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
- Michael T Goodric and Roberto Tamassia, “Algorithm Design: Foundations, Analysis and Internet Examples”, John Wiley and Sons, 2002.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, Third Edition, The MIT Press, 2009.
- SanjoyDasgupta, Christos Papadimitriou and UmeshVazirani, “Algorithms”, Tata McGraw-Hill, 2009.
- RK Ahuja, TL Magnanti and JB Orlin, “Network flows: Theory, Algorithms, and Applications”, Prentice Hall Englewood Cliffs, NJ 1993.
- Rajeev Motwani and PrabhakarRaghavan, “Randomized Algorithms”, Cambridge University Press, 1995.
| 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 |
