MCA203 - Design and Analysis of Algorithms |
UNIT I INTRODUCTION |
Introduction - Notion of Algorithm - 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 IIIDYNAMIC PROGRAMMING |
Computing a binomial coefficient - Warshall’s and Floyd’ algorithm - Optimal binary search tree -
Knapsack problem - Memory functions. |
UNIT IVBACKTRACKING 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 VNP- HARD AND NP-COMPLETE PROBLEMS |
P & NP problems - NP-complete problems - Approximation algorithms for NP-hard problems -
Traveling salesman problem - Knapsack problem. |
Reference Books |
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.
3. SaraBaase and Allen Van Gelder, “Computer Algorithms - Introduction to
Design and Analysis” Pearson education, 2003.
4. A.V.Aho, J.E Hopenfit and J.D.Ullman, “The Design and Analysis of Computer
algorithms” Pearson education Asia, 2003. |