Algorithm Analysis – Methodologies for Analyzing Algorithms, Asymptotic growth rates, Amortized Analysis. Array based structures, lists and. Advanced Data Structures – Dictionaries, hash tables, bloom filters, binary search trees, interval and range trees; skip lists.
Foundations and Applications of Divide-and-Conquer, Greedy techniques, Dynamic Programming, Backtracking and Branch and Bound. Applications of graph
algorithms: Topological sort, Strongly Connected Components, Bi-connected Components, Bridges, Articulation points. All Pair Shortest Paths, Single Source Shortest Paths.

Flow Networks: Ford-Fulkerson, Edmonds Karp, Applications of maximum flows – Efficient algorithms for maximum bipartite matching. NP-Completeness: Important NP-Complete Problems, Polynomial time reductions, Approximation algorithms, Parallel Algorithms (overview): Tree Contraction – Divide and Conquer – Maximal Independent Set.

Pre-Requisite(s): Foundations of Data Structures and Algorithms, Programming Paradigms and Problem Solving
Course Type: Lab

Course Objectives

1. Gain an in-depth knowledge of advanced data structures viz., hash tables, bloom filters and skip lists
2. Improve the efficiency of algorithms for different data structures to enhance performance in real-world applications.
3. Strengthen critical thinking and problem-solving skills by analyzing complex problems and devising efficient solutions using various algorithmic techniques.

Course Outcomes

• CO1: Comprehend the theoretical foundations of algorithm analysis and analyze the complexity of data structures and algorithms.
• CO2: Apply advanced data structures for real-world problem-solving.
• CO3: Employ various algorithm design techniques for solving real-world problems.
• CO4: Evaluate the complexity classes of various problems and relate them to classical problems.

CO-PO Mapping

Evaluation Pattern: 70/30

Note: Continuous assessments can include quizzes, tutorials, lab assessments, case study and project reviews. Midterm and End semester exams can be a theory exam or lab integrated exam for two hours.

1. Goodrich M T, Tamassia R and Michael H. Goldwasser, “Data Structures and Algorithms in Python++”, Wiley publication, 2013.
2. Cormen T H, Leiserson C E, Rivest R L and Stein C. Introduction to Algorithms, Prentice Hall of India Private Limited, Third Edition; 2009.
3. Michael T Goodrich and Roberto Tamassia, “Algorithm Design and Applications”, John Wiley and Sons, 2014.
4. Motwani R, Raghavan P. Randomized algorithms. Cambridge university press; 1995.
5. Udi Manber, “Algorithms : A Creative Approach”, Pearson, First Edition, 1989.
6. Vijay V. Vazirani. Approximation Algorithm, Springer; 2003.
7. Steven S.Skiena, “The Algorithm Design Manual”, Springer, Third Edition, 2020.