B.Tech. III Year I Sem. L T P C 3 1 0 4 Prerequisites: 1. A course on “Programming for Problem Solving and Data Structures”. 2. A course on “Advanced Data Structures”. Course Objectives:  Introduces the notations for analysis of the performance of algorithms and the data structure of disjoint sets.  Describes major algorithmic techniques (divide-and-conquer, backtracking, dynamic programming, greedy, branch and bound methods) and mention problems for which each technique is appropriate  Describes how to evaluate and compare different algorithms using worst-, average-, and best case analysis.  Explains the difference between tractable and intractable problems, and introduces the problems that are P, NP and NP complete. Course Outcomes:  Analyze performance of Algorithms using Asymptotic Notations  Design and Analyze the algorithms for solving complex problems using Divide-and-Conquer, backtracking, Greedy, Dynamic Programming and Branch & Bound Techniques.  Choose appropriate data structures and algorithm design methods for a specified application  Explain how the choice of data structures and the algorithm design methods impact the performance of programs  Find the optimal solution of complex problems in Graphs  Develop profound understanding of P,NP,NP-Hard and NP-Complete problems UNIT - I Introduction: Algorithm, Performance Analysis-Space complexity, Time complexity, Asymptotic Notations- Big oh notation, Omega notation, Theta notation and Little oh notation. Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort, Strassen‟s matrix multiplication. UNIT - II Disjoint Sets: Disjoint set operations, union and find algorithms, Heaps- Min, Max, Priority Queue, Heapsort Backtracking: General method, applications, n-queen‟s problem, sum of subsets problem, graph Coloring, Hamiltonian cycles. UNIT - III Dynamic Programming: General method, applications- Optimal binary search tree, 0/1 knapsack problem, All-pairs shortest path problem, Traveling salesperson problem, Reliability design. UNIT - IV Greedy method: General method, applications-Job sequencing with deadlines, knapsack problem,