Back close

Course Detail

Course Name Advanced Algorithms and Analysis
Course Code 19CSE459
Program B. Tech. in Electronics and Computer 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, AhoCorasick, 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. NP-Completeness: 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 – Cache-oblivious Algorithms for Matrix Multiplication and Binary Search.

Objectives and Outcomes

Course Objectives

  • This course introduces students to advanced techniques for the design and analysis of algorithms and explores a variety of applications.

Course Outcomes

  • CO1: Understand various methodology for analyzing the algorithms.
  • CO2: Apply different graph algorithms and analyze its Complexity.
  • CO3: Analyze various algorithm design techniques and solve different problems using those techniques and analyse its Complexity.
  • CO4: Evaluate the performance of various Network flow algorithms.
  • CO5: Understand NP completeness and Polynomial Reduction Techniques.

CO – PO Mapping

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2
CO1 2 1 3 2 2 3 2
CO2 3 1 2 2 3 2 2 2 3 2
CO3 3 3 2 3 3 2 2 3 3 2
CO4 3 2 2 2 3 2 2 2 3 2
CO5 3 3 2 3 2 2 3 2

Textbook / References


  • 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.
  • Motwani R, Raghavan P. Randomized algorithms. Cambridge university press; 1995.
  • Vijay V. Vazirani. Approximation Algorithm, Springer; 2003.

Evaluation Pattern

Assessment Internal External
Periodical 1 15
Periodical 2 15
*Continuous Assessment (CA) 20
End Semester 50
*CA – Can be Quizzes, Assignment, Projects, and Reports.

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