MC9223-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. |