Course

Syllabus

Algorithm Analysis: Methodologies for analyzing algorithms, asymptotic growth rates, and amortized analysis. Fundamental Data Structures: Array-based structures and linked lists. Advanced Data Structures: Dictionaries, hash tables, Bloom filters, binary search trees, interval trees, range trees, and skip lists.

Algorithm Design Techniques: Foundations and applications of Divide-and-Conquer, Greedy techniques, Dynamic Programming, Backtracking, and Branch and Bound. Graph Algorithms: Topological sorting, strongly connected components, bi-connected components, bridges, articulation points, single-source shortest paths, and all-pairs shortest paths.

Flow Networks: Ford–Fulkerson algorithm, Edmonds–Karp algorithm, and applications of maximum flow, including efficient algorithms for maximum bipartite matching. Computational Complexity: NP-completeness, important NP-complete problems, polynomial-time reductions, and approximation algorithms. Parallel Algorithms (Overview): Tree contraction, parallel Divide-and-Conquer, and maximal independent set algorithms.

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

Course Type: Lab

Course Objectives

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

Course Outcomes

CO-PO Mapping

Evaluation Pattern: 70/30

Note: Continuous assessment may include quizzes, tutorials, programming assignments, algorithm design and analysis exercises, case studies, laboratory assessments, and project reviews. The Mid-Term examination and the End-Semester examination may be conducted as a two-hour written examination or a laboratory-integrated examination, based on the course requirements.

1. Data Structures and Algorithms in Python, Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser, John Wiley & Sons, 2013.
2. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 3rd ed., Prentice Hall of India, 2009.
3. Algorithm Design and Applications, Michael T. Goodrich and Roberto Tamassia, John Wiley & Sons, 2014.
4. Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995.
5. Introduction to Algorithms: A Creative Approach, Udi Manber, Addison-Wesley, 1989.
6. Approximation Algorithms, Vijay V. Vazirani, Springer, 2003.
7. The Algorithm Design Manual, Steven S. Skiena, 3rd ed., Springer, 2020.