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
Reference Book:
R. C. T. Lee, S. S. Tseng, R.C. Chang and T. Tsai (2006), Introduction to Design and Analysis of Algorithms A strategic approach, McGraw Hill, India. Allen Weiss (2009), Data structures and Algorithm Analysis in C++, 2nd edition, Pearson education, New Delhi. Aho, Ullman, Hopcroft (2009), Design and Analysis of algorithms, 2nd edition, Pearson education, New Delhi
Text Book:
Ellis Horowitz, Satraj Sahni, Rajasekharam (2007), Fundamentals of Computer Algorithms, 2nd edition, University Press, New Delhi.
