Back close

Course Detail

Course Name Advanced Algorithms and Analysis
Course Code 15CSE331
Program B. Tech. in Computer Science and Engineering
Year Taught 2019


Unit 1

Algorithm Analysis- Methodologies for Analyzing Algorithms, Asymptotic growth rates, Amortized Analysis. Number Theory: Preliminaries, FLT, Euclid’s algorithm (extended). Totient function, Sieve for primes, Inverse modulo n, Modular exponentiation, Applications of graph algorithms: Topological sort, Strongly Connected Components, Bi-connected Components, Bridges, Articulation points. All Pair Shortest Paths, Single Source Shortest Paths. Computational Geometry: Convex Hull, closest pair of points in 2D, the triangle with smallest perimeter in 2D, Determining whether a set of line segments have one or more intersections.

Unit 2

Applications of Divide-and-Conquer, Greedy techniques and Dynamic Programming – Knapsack, Median finding, Scheduling algorithms, Party planning, bitonic TSP etc., String matching algorithms: KMP, Rabin Karp, Aho-Corasick, 2D queries, efficient algorithms for longest palindrome, Longest Common Substring.

Unit 3

Flow Networks: Ford-Fulkerson, Edmonds Karp, Applications of maximum flows – Efficient algorithms for maximum bipartite matching, minimum cost matching. NPCompleteness: Important NP-Complete Problems, Polynomial time reductions, Approximation algorithms, Parallel Algorithms (overview): Tree Contraction – Divide and Conquer – Maximal Independent Set. External-Memory Algorithms – Accounting for the Cost of Accessing Data from Slow Memory – Sorting – B-trees – Cacheoblivious Algorithms for Matrix Multiplication and Binary Search.

Text Books

  • Goodrich M. T. and Tamassia R., “Algorithm Design and Applications”, John Wiley and Sons, 2014.


  • Cormen T. H., Leiserson C. E., Rivest R. L. and Stein C., “Introduction to Algorithms”, Prentice Hall of India Private Limited, Third Edition, 2009
  • Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms”, Cambridge University Press, 1995.
  • Vijay V. Vazirani., “Approximation Algorithm”, Springer, 2003

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