Design & Analysis Of Algorithms

Front Cover
Technical Publications, Jan 1, 2007 - 317 pages
1 Review
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.

Contents

Chapter4 Dynamic Programming 41 to 4 32
4-1
CHapter6 Backtracking __ 5 1 to 6
6-1
Chapter7 Branch and Bound 71 to 728
7-1
Chapier8 NP hard and NP Cotnplete Problems 81 to 810
8-1
v1
P-30

Other editions - View all

Common terms and phrases

Bibliographic information