Syllabus Analysis of Algorithm - (2113113) Theory Term work Pract / Oral Total Internal Assessment End Sem Exam Exam Duration (in Hrs) Test 1 Test 2 IAT - I + IAT - II (Total) 20 20 40 60 2 - - - - 100 Sr. No. Name of Module Detailed Content 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. Self-learning Topics : Complexity class : Definition of P, NP, NP-Hard, NP-Complete. (Chapter - 1) 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, real life applications of all algorithms. (Chapter - 2) III. Greedy Method Approach General Method, Single source shortest path : Dijkstra Algorithm Fractional Knapsack problem, Minimum cost spanning trees : Kruskal and Prim’s algorithms. Self-learning Topics : Job sequencing with deadlines, real life applications of all algorithms. (Chapter - 3) IV. Dynamic Programming Approach General Method, Multistage graphs, All pair shortest path : Floyd Warshall Algorithm, 0/1 knapsack Problem, Travelling Salesperson problem, Longest common subsequence. Self-learning Topics : Bellman Ford Algorithm, real life applications of all algorithms. (Chapter - 4) V. Backtracking and Branch and bound General Method, Backtracking : n-queen problem, Sum of subsets, Graph coloring. Branch and Bound : Travelling Salesperson Problem, 15 Puzzle problem. Self-learning Topics : Real life applications of all algorithms. (Chapters - 5, 6) VI. String Matching Algorithms The Naïve string-matching algorithm, The Rabin Karp algorithm, The Knuth-Morris-Pratt algorithm. Self-learning Topics : Real life applications of all algorithms. (Chapter - 7)
