Design and Analysis of Algorithms
“In this page, Design and Analysis of Algorithms, we have provided the complete syllabus along with detailed notes for all the points.”
Design and Analysis of Algorithms
Unit I: Design and Analysis of Algorithms
- Introduction to Algorithms
- Design and Performance Analysis of Algorithms
- Time Complexity
- Space Complexity
- Asymptotic Notations
- Big-O Notation (O)
- Omega Notation (Ω)
- Theta Notation (Θ)
- Applications of Asymptotic Notations
- Algorithm Analysis
- Sequential Search
- Bubble Sort
- Selection Sort
- Insertion Sort
- Matrix Multiplication
- Recursion: Basic Concepts
- Analysis of Recursive Algorithms
- Master’s Theorem
Unit II: Divide and Conquer Design Technique
- Basic Concept of Divide and Conquer
- Binary Search
- Finding Maximum and Minimum
- Merge Sort
- Quick Sort
- Best and Worst Case Analysis
- Strassen’s Matrix Multiplication
- Lower Bound for Comparison-Based Sorting
Greedy Design Technique
- General Concept of Greedy Method
- Knapsack Problem (Greedy Approach)
- Minimum Spanning Tree
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm – Single Source Shortest Path
Unit III: Dynamic Programming Design Technique
- General Concept of Dynamic Programming
- Fibonacci Series (DP Approach)
- Computation of Binomial Coefficients
- All-Pair Shortest Path – Floyd-Warshall Algorithm
- 0/1 Knapsack Problem (DP Approach)
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Finding Connected Components
- DFS of a Directed Graph
- Topological Sorting
Unit IV: Limitations of Algorithmic Power
- Backtracking Method
- n-Queen Problem
- Sum of Subsets Problem
- Hamiltonian Circuit Problem
- Vertex Cover Problem
- Computational Intractability
- Overview of Non-deterministic Algorithms
- Class P Problems
- Class NP Problems
- NP-Complete Problems
- NP-Hard Problems