CS8451 – NOTES & QP
| NOTES | CLICK HERE |
| SEMESTER QP | CLICK HERE |
CS8451 – SYLLABUS
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.