Algorithm, pseudo code for expressing algorithms, performance analysis-space complexity, time complexity, asymptotic notation- big (O) notation, omega notation, theta notation and little (o) notation, recurrences, probabilistic analysis, disjoint set operations, union and find algorithms. LAB SUM OF SUB SETS PROBLEM Find a subset of a given setS = {sl, s2, ,sn} of n positive integers whose sum is equal to a given positive integer d.

General method, applications-analysis of binary search, quick sort, merge sort, AND OR Graphs. GREEDY METHOD: General method, Applications-job sequencing with deadlines, Fractional knapsack problem, minimum cost spanning trees, Single source shortest path problem. LAB SORTING 1. Sort a given set of elements using the Quick sort method and determine the time required to sort the elements. 2. Implement merge sort algorithm to sort a given set of elements and determine the time required to sort the elements

Breadth first search and traversal, Depth first search and traversal, Spanning trees, connected components and bi-connected components, Articulation points. DYNAMIC PROGRAMMING: General method, applications - optimal binary search trees, 0/1 knapsack problem, All pairs shortest path problem, Travelling sales person problem, Reliability design. LAB TRAVELLING SALES PERSON PROBLEM 1. Implement any scheme to find the optimal solution for the Traveling Sales Person problem.

General method, Applications- n-queen problem, Sum of subsets problem, Graph coloring and Hamiltonian cycles. BRANCH AND BOUND: General method, applications - travelling sales person problem, 0/1 knapsack problem- LC branch and bound solution, FIFO branch and bound solution. LAB KNAPSACK PROBLEM Implement 0/1 Knapsack problem using Dynamic Programming

Basic concepts, non-deterministic algorithms, NP-hard and NP-complete classes, Cook‘s theorem. LAB N QUEENS PROBLEM Implement N Queen's problem using Back Tracking