Design and Analysis of Algorithms
🔹 UNIT 1: Foundation of Algorithm Analysis
What is an algorithm? Explain the properties of an algorithm.
Why do we need algorithms?
Explain the RAM model with a suitable example.
Define time and space complexity.
Explain best, worst, and average case complexity.
Explain aggregate analysis with example.
Explain Big-O notation with example.
Explain Big-Ω notation with example.
Explain Big-Θ notation with example.
Compare Big-O, Big-Ω, and Big-Θ.
Explain geometrical interpretation of asymptotic notations.
What is a recurrence relation?
Solve recurrence using recursion tree method.
Solve recurrence using substitution method.
Solve recurrence using Master’s theorem.
Solve: ( T(n) = 2T(n/2) + 1 )
Solve: ( T(n) = T(n-1) + 1 )
🔹 UNIT 2: Iterative Algorithms
Write an iterative algorithm to find factorial and analyze it.
Write an algorithm to find the nth Fibonacci number and analyze it.
Explain Euclid’s algorithm for GCD.
Define sequential search. Write its algorithm and analyze it.
Write algorithm for bubble sort and analyze it.
Write algorithm for selection sort and analyze it.
Write algorithm for insertion sort and analyze it.
Compare bubble sort, selection sort, and insertion sort.
🔹 UNIT 3: Divide and Conquer Algorithms
Explain divide and conquer strategy with example.
Write recursive algorithm for binary search and analyze it.
Write min-max algorithm using divide and conquer and analyze it.
Write merge sort algorithm and analyze its complexity.
Write quick sort algorithm and analyze best, worst, and average case.
What is the worst case of quick sort? How does randomized quick sort handle it?
Trace quick sort for a given array.
Explain heapify operation with example.
Write heap sort algorithm and analyze it.
Trace heap sort for given data.
Define order statistics problem.
Explain selection in expected linear time.
Explain selection in worst-case linear time.
🔹 UNIT 4: Greedy Algorithms
What is an optimization problem?
What is greedy strategy?
When does greedy algorithm give optimal solution?
Explain elements of greedy strategy.
Solve fractional knapsack problem using greedy method.
Write job sequencing with deadlines algorithm and analyze it.
Find minimum spanning tree using Kruskal’s algorithm.
Find minimum spanning tree using Prim’s algorithm.
Explain Dijkstra’s algorithm with complexity.
What is Huffman coding?
Construct Huffman codes for given frequencies.
Find total number of bits using Huffman coding.
🔹 UNIT 5: Dynamic Programming
What is dynamic programming?
Explain elements of dynamic programming.
Compare greedy algorithm and dynamic programming.
Compare recursion and dynamic programming.
Explain memoization strategy.
Compare dynamic programming and memoization.
Solve matrix chain multiplication using DP.
Find optimal parenthesization of matrix chain.
Find edit distance between two strings using DP.
Solve 0/1 knapsack problem using DP.
Explain Floyd-Warshall algorithm.
Find all-pairs shortest path using Floyd-Warshall algorithm.
Explain travelling salesman problem using DP.
🔹 UNIT 6: Backtracking
What is backtracking?
How does backtracking differ from recursion?
Solve subset sum problem using backtracking.
Trace subset sum algorithm for given set and sum.
Solve 0/1 knapsack problem using backtracking.
Explain N-queen problem using backtracking.
Analyze time complexity of backtracking algorithms.
Does backtracking give multiple solutions? Explain.
🔹 UNIT 7: Number Theoretic Algorithms
Explain Euclid’s algorithm and analyze it.
Explain extended Euclid’s algorithm and analyze it.
Why is extended Euclid’s algorithm used?
Solve modular linear equations.
Solve system of congruences using Chinese Remainder Theorem.
Explain Miller-Rabin randomized primality test.
Analyze complexity of Miller-Rabin test.
🔹 UNIT 8: NP-Completeness & Approximation Algorithms
Define tractable and intractable problems.
Explain polynomial time and super-polynomial time.
Define class P.
Define class NP.
Define NP-Hard problems.
Define NP-Complete problems.
State Cook’s theorem.
Explain problem reducibility.
Prove SAT is NP-Complete.
Prove vertex cover is NP-Complete.
Prove subset sum is NP-Complete.
What is approximation algorithm?
Explain approximation algorithm for vertex cover.
Explain approximation algorithm for subset sum.