Important Topics: Analysis of Algorithms
Important Topics for Analysis of Algorithms
1. Algorithm Complexity:
- Time and space complexity definitions with examples.
- Master theorem and recurrence relations (e.g., Merge Sort).
- Order of growth and asymptotic notations (Big-O, Omega, Theta).
2. Algorithmic Approaches:
- Differences: Greedy, Divide & Conquer, Dynamic Programming.
- Randomized Algorithms: Las Vegas vs Monte Carlo approaches.
3. Key Problems:
- 0/1 Knapsack problem and its variants.
- Minimum Spanning Tree (Prim's and Kruskal's algorithms).
- Cook's theorem; NP, NP-complete, NP-hard problems.
- Pattern Matching Algorithms (KMP, Rabin-Karp).
4. Graph Problems:
- Vertex Cover and Set Cover problems.
- Network flow (Ford-Fulkerson method).
- Hamiltonian cycle and Traveling Salesman Problem (TSP).
5. String Matching Algorithms:
- Prefix functions in KMP and their applications.
Page 1
Important Topics: Analysis of Algorithms
- Naive and Boyer-Moore algorithms.
6. Dynamic Programming Applications:
- Matrix chain multiplication.
- Longest Common Subsequence (LCS).
- Optimal parenthesization of matrix products.
7. Backtracking vs Branch and Bound:
- Differences and examples (e.g., N-Queen Problem).
8. Other Topics:
- Assignment problem and Quadratic assignment problem.
- Feasible vs Optimal solutions.
- Huffman coding for data compression.
Analytical and Problem-Solving Focus:
- Sorting algorithms (Quick Sort, Merge Sort with examples).
- Proving NP-completeness (e.g., 3-SAT problem, Hamiltonian Cycle).
- Advanced topics like multi-commodity flow, augmenting paths.
Recommended Practice:
Focus on problem-solving strategies and derivations of algorithms (e.g., Strassen's Matrix
Multiplication).
Page 2
