ADVANCED ALGORITHMS ANALYSIS IMPORTANT
QUESTIONS
✅ UNIT – 1: Sorting and Graph Algorithms
(Essay Questions)
1. Compare various sorting algorithms (Insertion, Merge, Quick, Heap, Counting, Radix)
with respect to:
o Time complexity (Best, Average, Worst)
o Space complexity
o Stability
o Practical applications
2. Explain Topological Sorting:
o Define DAG
o Describe Kahn’s algorithm and DFS-based algorithm
o Prove correctness
o Analyze time complexity
3. Explain Breadth First Search (BFS):
o Algorithm
o Proof that BFS finds shortest path in unweighted graph
o Time and space analysis
4. Describe Dijkstra’s Algorithm:
o Algorithm steps
o Proof of correctness
o Time complexity using different data structures
5. Explain Depth First Search (DFS) and its applications.
o Discovery/finish time
o Edge classification
o Time complexity
6. Explain how Strongly Connected Components (SCC) are computed using Kosaraju’s
algorithm.
o Proof of correctness
o Time analysis
7. What is Amortized Analysis?
o Explain Aggregate, Accounting and Potential methods
o Give an example (Dynamic array expansion or Stack with multipop)
✅ UNIT – 2: Greedy Method, Matroids and
Matching
1. Explain the Greedy Paradigm.
o Characteristics
o Greedy choice property
o Optimal substructure
2. Define a Matroid.
o Properties
o Prove that greedy algorithm works for matroids
o Algorithm for maximum weight maximal independent set
3. Explain the application of Matroids in Minimum Spanning Tree (MST).
4. Describe algorithms for Minimum Spanning Tree (Kruskal and Prim).
o Correctness proof
o Time complexity
5. Define Graph Matching.
o Maximum Matching problem
o Augmenting path characterization theorem
6. Explain Edmonds’ Blossom Algorithm:
o Need for blossom contraction
o Algorithm outline
o Complexity analysis
✅ UNIT – 3: Flow Networks and Matrix
Computations
1. Define Flow Network.
o Explain Maxflow-Mincut Theorem
o Provide proof
2. Explain Ford-Fulkerson Algorithm:
o Algorithm
o Proof of correctness
o Time complexity
3. Describe Edmond-Karp Algorithm and compare it with Ford-Fulkerson.
4. Explain Strassen’s Matrix Multiplication Algorithm:
o Divide and Conquer approach
o Recurrence relation
o Time complexity derivation
5. Explain how to compute Inverse of a Triangular Matrix.
6. Describe LUP Decomposition:
o Algorithm
o Application in solving linear equations
7. Explain the relationship between time complexities of:
o Matrix multiplication
o Matrix inversion
o Linear system solving
✅ UNIT – 4: Dynamic Programming,
Number Theory & FFT
1. Explain Floyd-Warshall Algorithm:
o Dynamic programming formulation
o Correctness proof
o Time complexity
2. Explain the Dynamic Programming Paradigm:
o Characteristics
o Comparison with Divide and Conquer
o Examples (Knapsack, LCS)
3. State and prove the Chinese Remainder Theorem (CRT).
4. Explain:
o Base representation of integers
o Modulo representation
o Conversion between them
5. Extend CRT to Polynomials.
6. Explain Interpolation Problem and its solution using modular arithmetic.
7. Define Discrete Fourier Transform (DFT):
o DFT in complex field
o DFT in modulo ring
8. Explain Fast Fourier Transform (FFT):
o Divide and Conquer strategy
o Recurrence relation
o Time complexity
9. Explain Schonhage-Strassen Integer Multiplication Algorithm and its complexity.
✅ UNIT – 5: Linear Programming and NP-
Completeness
1. Explain Linear Programming:
o Geometry of feasible region
o Convex sets and extreme points
2. Describe the Simplex Algorithm:
o Pivot operation
o Tableau method
o Time complexity
3. Define classes P, NP, NP-Hard and NP-Complete.
4. Explain the concept of Polynomial Time Reduction.
5. Prove that a problem is NP-Complete (e.g., SAT or CLIQUE).
6. Explain Cook’s Theorem and its significance.
7. Discuss recent trends in:
o Advanced searching techniques
o Advanced sorting techniques
o New data structures for efficient problem solving
🎯 Highly Repeated / Very Important Essay
Topics
⭐ Dijkstra with proof
⭐ Maxflow-Mincut theorem
⭐ Floyd-Warshall
⭐ FFT algorithm
⭐ Strassen’s algorithm
⭐ NP-Completeness proof
⭐ Matroids and greedy proof
⭐ Edmonds Blossom algorithm