Course

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.

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

Textbook(s)

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

Reference(s)

• 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