Please enable JavaScript.
Coggle requires JavaScript to display documents.
Analysis of Algorithm (Introduction to analysis of algoritm (Recurrences:,…
Analysis of Algorithm
Introduction to analysis of algoritm
Decision and analysis fundamentals
• Performance analysis , space and time complexity
Growth of function – Big –Oh ,Omega , Theta notation
Mathematical background for algorithm analysis,
Analysis of selection sort , insertion sort.
Recurrences:
The substitution method
-Recursion tree method
-Master method
Divide and Conquer Approach:
General method
Analysis of Merge sort, Analysis of Quick sort, Analysis of Binary search,
Finding minimum and maximum algorithm and analysis, Strassen‟s matrix
multiplication
Dynamic Programming Approach:
General Method
Multistage graphs
single source shortest path
all pair shortest path
Assembly-line scheduling
0/1 knapsack
Travelling salesman problem
Longest common subsequence
*Greedy Method Approach
:
General Method
Single source shortest path
Knapsack problem
Job sequencing with deadlines
Minimum cost spanning trees-Kruskal and prim‟s algorithm
Optimal storage on tapes
Backtracking and Branch-and-bound:
General Method
8 queen problem( N-queen problem)
Sum of subsets
Graph coloring
15 puzzle problem,
Travelling salesman problem
String Matching Algorithms:
The naïve string matching Algorithms
The Rabin Karp algorithm
String matching with finite automata
The knuth-Morris-Pratt algorithm
Non-deterministic polynomial algorithms:
Polynomial time,
Polynomial time verification
NP Completeness and reducibility
NP Completeness proofs
Vertex Cover Problems
Clique Problems