Please enable JavaScript.
Coggle requires JavaScript to display documents.
Design and Analysis of Algorithms (Notion of NP-completeness (P class, NP…
Design and Analysis of Algorithms
Lower Bound Theory
O(nlgn) bound for comparison sort
Disjoint set manipulation
Set manipulation algorithm
UNION-FIND
Union by rank
Complexity Analysis
Time and Space Complexity
Different Asymptotic notations
Graph traversal algorithm: Recapitulation
BFS(Breadth First Search)
DFS(Depth First Search)
Classification of edges
Tree
Forward
Back
Cross Edge
Algorithms Design Techniques
Divide and Conquer
Dynamic Programming
Basic method
8 queens problem
Greedy Method
Graph coloring problem
Basic method
Matrix Chain Manipulation
All pair shortest paths
Backtracking:
Single source shortest
Basic method
Knapsack problem
Job sequencing with deadlines
Minimum cost spanning
Prim’s Algorithm
Kruskal’s algorithm.
Basic method
Binary Search
Merge Sort
Quick Sort
Heap Sort
String matching problem
Different techniques
Naive algorithm
string matching using finite automata
Knuth
Morris
Pratt
KMP
Amortized Analysis
Aggregate
Accounting
Potential Method
Network Flow
Ford Fulkerson algorithm
Max-Flow Min-Cut theorem
Matrix Manipulation Algorithm
Strassen’s matrix manipulation algorithm
LUP decomposition
Inversion of matrix
Boolean matrix multiplication
Notion of NP-completeness
P class
NP class
NP hard class
NP complete class
Satisfiability problem
Cook’s
theorem
Clique decision problem
Approximation Algorithms
Necessity of approximation scheme
performance guarantee
polynomial time approximation schemes
vertex cover problem
Travelling salesman problem