COURSE SUMMARY
Course Title:
Advanced Algorithms and Analysis
Course Code:
15CSE331
Year Taught:
2015
2016
2017
2018
Type:
Elective
Degree:
School:
School of Engineering
Campus:
Bengaluru
Chennai
Coimbatore
Amritapuri

'Advanced Algorithms and Analysis' is a course offered in the B. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.

#### SYLLABUS

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.

#### TEXTBOOK

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

#### REFERENCES

• 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