Design & Analysis Of Algorithms
IntroductionAlgorithm, Psuedo code for expressing algorithms, Performance Analysis - Space complexity, Time complexity, Asymptotic Notation - Big oh notation, Omega notation, Theta notation and Little oh notation, Probabilistic analysis, Amortized analysis.Divide and ConquerGeneral method, Applications-Binary search, Quick sort, Merge sort, Strassen's matrix multiplication.Greedy methodGeneral method, applications - Job sequencing with dead lines, 0/1 knapsack problem, Minimum cost spanning trees, Single source shortest path problem.Dynamic programmingGeneral method, Applications - Matrix chain multiplication, Optimal binary search trees, 0/1 knapsack problem, All pairs shortest path problem, Travelling sales person problem, Reliability design.Searching and Traversal techniquesEfficient non recursive binary traversal algorithms, Graph traversal Breadth first search and Depth first search, AND/OR graphs, Game tree, Bi-connected components.BacktrackingGeneral method, Applications-n-queen problem, Sum of subsets problem, Graph coloring, Hamilitonian cycles.Branch and BoundGeneral method, applications - Travelling sales person problem, 0/1 knapsack problem, LC Branch and Bound solution, FIFO Branch and Bound solution.NP-Hard and NP-complete problemsBasic concepts, Non deterministic algorithms, NP-Hard and NP-complete classes, Cook's theorem.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Chapter4 Dynamic Programming 41 to 4 32
CHapter6 Backtracking __ 5 1 to 6
Chapter7 Branch and Bound 71 to 728
Chapier8 NP hard and NP Cotnplete Problems 81 to 810
Other editions - View all
0/1 knapsack problem 16 Marks adjacent amortized analysis answer node array articulation point backtracking becomes E-node bi-connected components binary search tree binary tree boolean bound method bounding function branch and bound CA(X column compute Cook's Theorem Cost of node denotes deterministic algorithm divide and conquer dynamic programming edge example feasible sequence feasible solution fixed tuple graph coloring graph G Hamiltonian cycle Hence initially inorder input kill node left child list of live live nodes logn matrix merge sort minimum cost minimum spanning tree notation NP-complete NP-hard object obtained optimal binary search optimal solution optimum cost partition postorder Prim's algorithm printf profit queens quick sort recursive Refer section right child root selected shortest path space tree Step subarray sublist sum of subset Total weight travelling salesperson problem traversal tuple size formulation vertex vertices Write an algorithm