Design & Analysis Of Algorithms
Technical Publications, 2007 - 317 pages
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.