COURSE SUMMARY
Course Title: 
Practical Algorithms for Programmers
Course Code: 
18SN601
Year Taught: 
2018
Semester: 
1
Degree: 
Postgraduate (PG)
School: 
School of Engineering
Center: 
Cyber Security
Campus: 
Amritapuri

"Practical Algorithms for Programmers" is a course offered in the first semester of M. Tech. in Cyber Security Systems & Networks program at School of Engineering, Amrita Vishwa Vidyapeetham, Amritapuri.

Algorithm Analysis: Asymptotic Notation-Standard - Recurrences - Solution to Recurrences Divide and Conquer - Sorting, Matrix Multiplication and Binary Search. Dynamic Programming- Longest common sustring/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.

  1. Michael T Goodrich, 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. R. K. Ahuja, TL Magnanti, 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.