**MC 9223 DESIGN AND ANALYSIS OF ALGORITHMS**

**UNIT I INTRODUCTION**

**Fundamentals of algorithmic problem solving – Important problem types –**

**Fundamentals of the analysis of algorithm efficiency – analysis frame work –**

**Asymptotic notations – Mathematical analysis for recursive and non-recursive**

**algorithms.**

**UNIT II DIVIDE AND CONQUER METHOD AND GREEDY METHOD**

**Divide and conquer methodology – Merge sort – Quick sort – Binary search – Binary**

**tree traversal – Multiplication of large integers – Strassen’s matrix multiplication –**

**Greedy method – Prim’s algorithm – Kruskal’s algorithm – Dijkstra’s algorithm.**

**UNIT III DYNAMIC PROGRAMMING**

**Computing a binomial coefficient – Warshall’s and Floyd’ algorithm – Optimal binary**

**search tree – Knapsack problem – Memory functions.**

**UNIT IV BACKTRACKING AND BRANCH AND BOUND**

**Backtracking – N-Queens problem – Hamiltonian circuit problem – Subset sum problem**

**– Branch and bound – Assignment problem – Knapsack problem – Traveling**

**salesman problem.**

**UNIT V NP-HARD AND NP-COMPLETE PROBLEMS**

**P & NP problems – NP-complete problems – Approximation algorithms for NP-hard**

**problems – Traveling salesman problem – Knapsack problem.**

**REFERENCES:**

**1. Anany Levitin “Introduction to the Design and Analysis of Algorithms” Pearson**

**Education 2003.**

**2. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, “Introduction to**

**algorithms” Prentice Hall 1990.**