Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types –Fundamentals of the Analysis of Algorithm Efficiency – Analysis Framework – Asymptotic Notations and its properties – Mathematical analysis for Recursive and Non recursive algorithms. Lab component: 1. Implement GCD using Euclidian algorithm 2. Implement Towers of Hanoi problem and analyze it

Brute Force: Selection sort, Bubble Sort, Sequential Search, Closest-Pair and Convex-Hull Problems-TravelingSalesmanProblem–KnapsackProblem-Assignmentproblem.Divideandconquermethodology: Merge sort – Quick sort – Binary search – Multiplication of Large Integers – Strassen’s Matrix Multiplication Lab component: 1. Find the sorting mechanism which uses the pivot value as the key component to sort all the values.Writealgorithmandderivethetimecomplexity.Sortthefollowingusingthesamemethod:45, 67, 12, 34, 09 2. Find the sorting mechanism which exactly divides the given problem into two proper subsets during the iteration. Write the algorithm and derive the time complexity. Sort the following using the same method. 45, 67, 12, 34, 09 3. Design an algorithm which always reduces the searching process by half based on the root node value in the constructed tree. Write the algorithm and time complexity. Construct the tree for applying the above algorithm using the same properties:55, 63, 31, 17, 22, 40, 67, 83

Dynamic Programming: Computing a Binomial Coefficient– Warshall’s and Floyd’s algorithm –Optimal Binary Search Trees – Knapsack Problem and Memory functions. Greedy Technique Prim’salgorithm-Kruskal'sAlgorithm-Dijkstra'sAlgorithm-HuffmanTrees– Job Sequence Scheduling Lab Component: 1. Design an algorithm which should give an optimal solution always in finding minimum spanning tree. Write an algorithm and time complexity. 2. Userwantstosendhisdatainsecuredmannerfromoneplacetoanotherplacethroughcommunication channel. His encoding mechanism should support variable length encoding mechanism. Design an algorithm for this situation to solve the user problem and write the time complexity. 3. User wants to find shortest path between all the vertices. Give solution to the user using dynamic programming methodology, Write an algorithm and time complexity.

Flow Networks-Ford Fulkerson Method-String Matching-Naive String Matching Algorithm-Knuth Morris Pratt Algorithm-Analysis Lab Component 1. Implement Naïve String Matching Algorithm 2. Implement ford Fulkerson algorithm

Limitations of Algorithm-Lower-Bound Arguments-Decision Trees-P, NP and NP- Complete Problems – Coping with the Limitations – Backtracking: n-Queens problem – Hamiltonian Circuit Problem –Subset Sum Problem-Branch and Bound: Assignment problem–Knapsack Problem–Traveling Salesman Problem-Approximation Algorithms for NP Hard Problems Lab Component 1. Implement knapsack problem using branch and bound. 2. Implement any scheme to find the optimal solution for the Traveling Sales Person problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation. 3. Design and implement in Java to find a subset of a given set S = {Sl, S2, ....., Sn} of n positive integers whose SUM is equal to a given positive integer d. For example, if S={1, 2, 5, 6, 8} and d= 9, there are two solutions {1, 2, 6}and {1, 8}. Display a suitable message, if the given problem instance doesn't have a solution.