**Subject Code:54016CSE L:3 T/P/D:1 Credits:3 Int. Marks:25 Ext. Marks:75 Total Marks:100**

**UNIT I: I**

**Introduction: Algorithm,Psuedo code for expressing algorithms,Performance Analysis-Space complexity, Time complexity, Asymptotic Notation- Big oh notation, Omega notation, Theta notation and Little oh notation,Probabilistic analysis, Amortized analysis.**

**UNIT II: II**

**Disjoint Sets- disjoint set operations, union and find algorithms, spanning trees, connected components and biconnected components.**

**UNIT III: III**

**Divide and conquer: General method , applications-Binary search, Quick sort, Merge sort, Strassen’s matrix multiplication.**

**UNIT IV: IV**

**Greedy method: General method, applications-Job sequencing with dead lines, 0/1 knapsack problem, Minimum cost spanning trees, Single source shortest path problem.**

**UNIT V: V**

**Dynamic Programming: General method, applications-Matrix chain multiplication, Optimal binary search trees, 0/1 knapsack problem, All pairs shortest path problem,Travelling sales person problem, Reliability design.**

**UNIT VI: VI**

**Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph coloring, Hamiltonian cycles.**

**UNIT VII: VII**

**Branch and Bound: General method, applications - Travelling sales person problem,0/1 knapsack problem- LC Branch and Bound solution, FIFO Branch and Bound solution.**

**UNIT VIII: VIII**

**NP-Hard and NP-Complete problems: Basic concepts, non deterministic algorithms, NP - Hard and NPComplete classes, Cook’s theorem.**

**TEXT BOOKS:**

**1. Fundamentals of Computer Algorithms, Ellis Horowitz,Satraj Sahni and Rajasekharam,Galgotia publications pvt. Ltd.**

**2. Design and Analysis Algorithms - Parag Himanshu Dave, Himanshu Bhalchandra Dave Publisher: Pearson**

**3. Algorithm Design: Foundations, Analysis and Internet examples, M.T.Goodrich and R.Tomassia,John wiley and sons.**

**REFERENCE BOOKS:**

**1. Introduction to Algorithms, secondedition,T.H.Cormen,C.E.Leiserson, R.L.Rivest,and C.Stein,PHI Pvt. Ltd./ Pearson Education**

**2. Introduction to Design and Analysis of Algorithms A strategic approach, R.C.T.Lee, S.S.Tseng, R.C.Chang and T.Tsai, Mc Graw Hill.**

**3. Data structures and Algorithm Analysis in C++, Allen Weiss, Second edition, Pearson education.**

**4. Design and Analysis of algorithms, Aho, Ullman and Hopcroft,Pearson education.**