Design and Analysis of Algorithm
Introduction: Algorithm, Pseudo 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 complexity.
Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort, Stassen’s Matrix Multiplication.
Searching and Traversal Techniques: Efficient non-recursive binary tree traversal algorithms, Disjoint set operations, union and find algorithms, Spanning trees, Graph
traversals- Breadth first search and Depth first search, AND/OR graphs, game trees, Connected Components, Bi-connected components.
Greedy method: General method, applications-Job sequencing with deadlines, knapsack problem, Minimum cost spanning trees, Single source shortest path problem.
Dynamic Programming: General method, applications-Multistage graphs, Optimal binary search trees,0/1 knapsack problem, All pairs shortest path problem, Traveling sales person problem, Reliability design.
Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph coloring, Hamiltonian cycles.
Branch and Bound: General method, applications - Traveling sales person problem,0/1 knapsack problem-LC Branch and Bound solution, FIFO Branch and Bound solution.
NP-Hard and NP-Complete problems: Basic concepts, Non-deterministic algorithms, NP - Hard and NP- Complete classes, NP-Hard problems, Cook's theorem.
The Design and Analysis of Computer Algorithms By Alfred V. Aho , John E. Hopcroft and Jeffrey D. Ullman