Back close

Course Detail

Course Name Advanced Algorithms and Analysis
Course Code 18CS631
Program
Credits Coimbatore
Year Taught 2018

Syllabus

Course Syllabus

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.

Course Outcome
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

Text Books

  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.

References

‘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.

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.

Admissions Apply Now