B.E Artificial Intelligence and Machine Learning Analysis of Algorithm Lab Syllabus - Mumbai University

Module 0: Prerequisite

• Basic knowledge of programming and data structure

Module I: Introduction

• Performance analysis- Master Method, space, and time complexity Growth of function, Big Oh, Omega Theta notation Mathematical background for algorithm analysis. Analysis of selection sort, insertion sort.

Module II: Divide and Conquer Approach

• General method, Merge sort, Quick sort, Analysis of Binary search. Self-learning Topics: Finding minimum and maximum algorithms and their Analysis, Strassen's Algorithm

Module III: Greedy Method Approach

• General Method, Single source shortest path: Dijkstra AlgorithmFractional Knapsack problem, Minimum cost spanning trees: Kruskal and Prim’s algorithms Self-learning Topics: Job sequencing with deadlines

Module 1: Assignment covers the topics from first three units limited to three Questions

Module 2: Assignment covers the topics from Last three units limited to three Questions

Module 1: Experiment based on common mathematical functions.( Selection sort, Insertion sort)

Module 2: Experiment based on divide and conquers approach. (Merge sort, Quick sort, Binary search)

Module 3

• Experiment based on greedy approach.( Single source shortest path- Dijkstra Fractional Knapsack problem, Minimum cost spanning trees-Kruskal and Prim’s algorithm)

Module 4: Experiment using dynamic programming approach (All pair shortest path- Floyd Warshall, 0/1 knapsack)

Module 5: Travelling salesperson problem Longest common subsequence

Module 6: Experiment based on graph Algorithms ( BFS, DFS , etc)

Module 7: Experiment using Backtracking strategy. (N-queen problem, Sum of subsets, Graph coloring)

Module 8: Experiment using branch and bound strategy.

Module 9

• Experiment based on string matching/amortized analysis (The Naïve string-matching Algorithms , The Rabin Karp algorithm, The Knuth-Morris-Pratt algorithm.

Module 10: Implementation Min-Max Algorithm

Module 11: Implementation of Job Sequencing with deadlines.

Module 12: Implementation of Bellman Ford Algorithm using Dynamic programming

Text Books

• 1 T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd Edition, PHI Publication 2005.
• 2 Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms” University Press.
• 1 Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGraw- Hill Edition.
• 2 S. K. Basu, “Design Methods and Analysis of Algorithm”, PHI Online Resources: