COURSE SUMMARY
Course Title: 
Advanced Algorithms and Analysis
Course Code: 
18CS631
Year Taught: 
2018
Degree: 
Postgraduate (PG)
School: 
School of Engineering
Campus: 
Coimbatore

'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

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