Design and Analysis of Algorithm

by A.A.PUNTAMBEKAR

Introduction Analysis of algorithm Analysis framework - Asymptotic notations - Analysis of non-recursive and recursive algorithms. Amortized analysis, Writing characteristic polynomial equations, Solving recurrence equations, Proof techniques : By contradiction, By mathematical induction, Direct proofs, Proof by counterexample, Proof by contraposition. Divide and Conquer and The Greedy Method Characteristic; Analysis Merge sort - Quick sort - Binary search - Large integer multiplication and Strassens matrix multiplication - Closest pair and convex Hull problems. The Greedy Method : General characteristics of greedy algorithms, Prims and kruskals Algorithms, Dijkstras algorithm, Huffman trees. Dynamic Programming General strategy, Principle of optimality, Warshalls and Floyds algorithm - Optimal binary search trees - Knapsack problem. Backtracking General method - Recursive backtracking algorithm, Iterative backtracking method. 8-queens problem, Sum of subsets and graph coloring, Hamiltonian cycle and Knapsack problem. Branch-Bound The method, Least cost search, FIFO branch and bound, LC branch and bound. 0/1 Kanpsack problem - LC branch and bound and FIFO branch and bound solution. Traveling sales person problem. NP-Hard and NP-Complete Problems Basic concepts, Non deterministic algorithms, The classes of NP hard and NP complete, Cooks theorem. NP-Complete problems - Satisfiability problem, Vertex cover problem. NP-Hard problems - Graph, Scheduling, Code generation problems, Simplified NP hard problems.

380 pages, Paperback

Published January 1, 2011