Introduction – Notion of algorithm – Fundamentals of algorithm problem solving – Important Problem types - Fundamentals of Analysis of algorithm efficiency: Analysis Framework – Asymptotic notations – Mathematical Analysis of non-recursive algorithms – Analysis of recursive algorithms: Substitution method, Recursion tree method and Master theorem Lab Practice: 1. Implement Greatest common divisor using Euclidean algorithm and Consecutive Integer checking method 2. Implement Tower of Hanoi problem using recursive and non-recursive method and analyze it

Brute force: Selection sort, Bubble sort, Sequential search, Closest pair and Convex Hull problems – Divide and conquer: Analysis of binary search, quick sort and merge sort – Multiplication of largest integers - Strassen’s matrix multiplication Lab Practice: 1. Implement a sorting mechanism which exactly divides the given problem into two proper subsets during the iteration. Write the algorithm and derive the time complexity. 2. Design an algorithm to find minimum number of coins (change) for a given value and analyze it.

Dynamic Programming: Computing a Binomial coefficient – Optimal Binary Search Tree (OBST) – 0/1 knapsack problem and memory function – Warshall’s and Floyd’s algorithm – Greedy Technique: Minimum spanning tree – Analysis of Prim’s and Kruskal algorithm – Shortest path: Analysis of Dijkstra’s algorithm – Huffman Trees Lab Practice: 1. Design an algorithm which should give an optimal solution always in finding a minimum spanning tree. Write an algorithm and derive time complexity. 2. Implement a Greedy algorithm for real world problem and analyze it

Flow Networks – Ford Fulkerson method – Maximum Matching in Bipartite Graphs – String matching: Naïve String matching algorithm – Knuth Morris Pratt algorithm – Rabin karp algorithm Lab Practice 1. Implement Naive String Matching Algorithm and analyze it 2. Implement Ford Fulkerson algorithm and analyze it

Limitations of algorithm power: Lower-Bound Arguments – Decision Trees – P, NP and NP complete problems – Backtracking: n-queens problem – Hamiltonian circuit problem – Branch and bound: Assignment problem – Knapsack problem – Travelling salesman problem – Approximation Algorithms for NP–hard problems (knapsack problem) Lab Practice: 1. Implement Hamiltonian circuit problem and analyze it 2. Implement polynomial time algorithms to verify NP Complete problems