Course

Algorithm Analysis – Methodologies for Analyzing Algorithms, Asymptotic growth rates, Amortized Analysis. Array based structures, lists and. Number Theory: Preliminaries, FLT, Euclid’s algorithm (extended), Totient function, Sieve for primes, Modular exponentiation.

Applications of Divide-and-Conquer, Greedy and Dynamic programming, Randomized techniques – Knapsack, Median finding, Scheduling algorithms, Party planning, bitonic TSP. String matching algorithms: Z Algorithm, KMP algorithm, Rabin-Karp, Universal hashing, consistent hashing, load balancing, power of two choices. Applications of graph algorithms: Topological sort, Strongly connected Components, Bi-connected Components, Bridges, Articulation points, All Pairs Shortest Paths, Single Source Shortest Paths.

Flow Networks: Ford-Fulkerson algorithm, Edmonds Karp algorithm, Applications of maximum flows – Maximum bipartite matching, minimum cost matching. Data Structures: Balanced binary trees, Suffix trees, Segment trees, Hash tables. Computational Geometry: Convex Hull, Closest pair of points. NP-Completeness: Important NP-Complete Problems, Polynomial time reductions, Approximation algorithms.

Preamble

This course builds upon the basic courses on data structures and algorithm design. It aims to enable students to design and adapt algorithms to solve complex problems especially relevant for AI domain. The focus will be on design and concrete implementations of various algorithmic techniques and their use in different application scenarios with proper analysis

Course Objectives

• To provide an understanding of algorithm design and analysis used in real life domain
• To solve complex problems by applying appropriate algorithmic design strategies
• To critically analyze the complexity of various algorithms
• To select appropriate design strategy to solve real world problems in AI domain

Course Outcomes

CO-PO Mapping

Prerequisites

• Basic Data Structures
• Basic Mathematics
• Basic Programming Language

Evaluation Pattern – 70:30

• Midterm Exam – 20%
• Continuous Evaluation – 50%
• End Semester Exam – 30%

Text Book / References

1. Cormen T H, Leiserson CE, Rivest R L and Stein C, “Introduction to Algorithms”, Prentice Hall of India Private Limited. Third Edition 2009.
2. Michael T Goodrich and Roberto Tamassia, “Algorithm Design and Applications”, Wiley, 2014.

1. Goodrich M T, Tamassia R and Michael H. Goldwasser, “Data Structures and Algorithms in Python++”, Wiley publication, 2013.

4. Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms”, Cambridge University Press, 1995.
5. Vijay V. Vazirani, “Approximation Algorithm”, Springer Science and Business Media, 2003.