Module I Algorithms and Complexity Introduction, Algorithm Complexity and various cases using Insertion Sort, Asymptotic Notations, Time complexity of Recursive Algorithm, Solving Recurrences using Iterative, Recursion Tree and Master Theorem.
Module II Divide and Conquer Discussion of basic approach using Binary Search, Merge Sort , Quick Sort , Selection in Expected linear time, Maximum Subarray , Matrix Multiplication , Introduction of Transform and Conquer and AVL Tree.
Module III Dynamic Programming Introduction and Approach, Rod Cutting, LCS, Optimal BST, Transitive closure and All-pair Shortest Path, Travelling Salesperson Problem.
Module IV Greedy and other Design Approaches Introduction to greedy using fractional knapsack, Huffman Code, Minimum Spanning Tree – Prim and Kruskal, Single Source Shortest Path Dijkstra’s and Bellman-Ford, Introduction to Backtracking using NQueens problem, Introduction to Branch and Bound using Assignment Problem or TSP.
Module V NP Completeness and Other Advanced Topics Non-deterministic algorithms – searching and sorting, Class P and NP, Decision and Optimization problem, Reduction and NPC and NPH, NP Completeness proof for: SAT, Max-Clique, Vertex Cover, Introduction to Randomized Algorithms, Introduction to Approximation Algorithms.