# [PDF] CS8451 Design and Analysis of Algorithms (DAA) 2017 Regulation Syllabus, Notes, 2 Marks, 2 Marks and 13 Marks, Question Banks/Important Questions and Previous years Question Papers for Anna University Students

Last updated on Sep 4, 2023

## Syllabus

CS8451 Design and Analysis of Algorithms

- UNIT I INTRODUCTION:Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types – Fundamentals of the Analysis of Algorithmic Efficiency –Asymptotic Notations and their properties. Analysis Framework – Empirical analysis - Mathematical analysis for Recursive and Non-recursive algorithms - Visualization
- UNIT II BRUTE FORCE AND DIVIDE-AND-CONQUER:Brute Force – Computing an – String Matching - Closest-Pair and Convex-Hull Problems - Exhaustive Search - Travelling Salesman Problem - Knapsack Problem - Assignment problem. Divide and Conquer Methodology – Binary Search – Merge sort – Quick sort – Heap Sort - Multiplication of Large Integers – Closest-Pair and Convex - Hull Problems.
- UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE:Dynamic programming – Principle of optimality - Coin changing problem, Computing a Binomial Coefficient – Floyd’s algorithm – Multi stage graph - Optimal Binary Search Trees – Knapsack Problem and Memory functions. Greedy Technique – Container loading problem - Prim’s algorithm and Kruskal's Algorithm – 0/1 Knapsack problem, Optimal Merge pattern - Huffman Trees.
- UNIT IV ITERATIVE IMPROVEMENT:The Simplex Method - The Maximum-Flow Problem – Maximum Matching in Bipartite Graphs, Stable marriage Problem.
- UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER:Lower - Bound Arguments - P, NP NP- Complete and NP Hard Problems. Backtracking – n-Queen problem - Hamiltonian Circuit Problem – Subset Sum Problem. Branch and Bound – LIFO Search and FIFO search - Assignment problem – Knapsack Problem – Travelling Salesman Problem - Approximation Algorithms for NP-Hard Problems – Travelling Salesman problem – Knapsack problem.

## Study Materials

Notes

1 | Notes | Download |

Question Banks/Important Questions