Comprehensive Algorithms Exam

Section A: Sorting Algorithms (25 points)

1. Apply Merge Sort to the array [8, 3, 5, 4, 7, 6, 1, 2]. Show the complete divide and conquer process with all
merge steps. (4 points)

2. Use Quick Sort with the first element as pivot to sort [6, 10, 13, 5, 8, 3, 2, 11]. Show partitioning steps. (3 points)

3. Apply Heapsort to [4, 10, 3, 5, 1]. First build max heap, then show extraction steps. (4 points)

4. Sort the array [3, 1, 4, 1, 5, 9, 2, 6] using Counting Sort. Assume values range from 1 to 9. (3 points)
5. Apply Bucket Sort to [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] using 4 buckets. (4 points)

6. Use Radix Sort to sort [170, 45, 75, 90, 2, 802, 24, 66]. Show each digit pass. (3 points)

7. Apply Insertion Sort to [5, 2, 4, 6, 1, 3]. Show each insertion step. (2 points)

8. Explain why Selection Sort has O(n²) time complexity in all cases while Bubble Sort can achieve O(n) in best
case. (2 points)
Section B: Dynamic Programming (30 points)

9. Rod Cutting Problem: Given rod length n=7 and prices p=[1,5,8,9,10,17,17,20], find maximum revenue using
bottom-up DP. Show the DP table. (6 points)

10. Matrix Chain Multiplication: Find optimal parenthesization for matrices A₁(5×10), A₂(10×3), A₃(3×12),
A₄(12×5). Show the m table and trace back optimal solution. (8 points)
11. Longest Common Subsequence: Find LCS of X="ABCDGH" and Y="AEDFHR". Show the DP table and trace
back the actual LCS. (8 points)

12. Activity Selection: Given activities with start times s=[1,3,0,5,8,5] and finish times f=[2,4,6,7,9,9], find maximum
number of non-overlapping activities using DP approach. (4 points)
 13. Compare the time complexities of naive recursive vs. bottom-up DP solutions for the Rod Cutting problem.
Explain why DP is more efficient. (4 points)

Section C: Greedy Algorithms (20 points)

14. Huffman Coding: Build optimal prefix code tree for characters with frequencies: A:45, B:13, C:12, D:16, E:9,
F:5. Show step-by-step construction and final codes. (8 points)
15. Activity Selection Greedy: Use the greedy algorithm for the same activities from question 12. Compare your
result with the DP solution. (4 points)

16. Kruskal's MST: Find minimum spanning tree for the graph with edges: (A,B,4), (A,H,8), (B,C,8), (B,H,11),
(C,D,7), (C,F,4), (C,I,2), (D,E,9), (D,F,14), (E,F,10), (F,G,2), (G,H,1), (G,I,6), (H,I,7). Show union-find
operations. (8 points)
Section D: Graph Algorithms (30 points)

17. BFS and DFS: Given adjacency list representation:

A: [B, C]
B: [A, D, E]
C: [A, F]
D: [B]
E: [B, F]
F: [C, E]

Perform BFS starting from A, then DFS starting from A. Show discovery/finish times for DFS. (6 points)

17. Topological Sort: Apply DFS-based topological sort to the DAG with vertices {shirt, tie, jacket, belt, watch,
undershorts, pants, shoes, socks} and dependencies: undershorts→pants→belt, undershorts→pants→shoes,
socks→shoes, shirt→tie→jacket, shirt→belt. (5 points)
19. Dijkstra's Algorithm: Find shortest paths from vertex A in the graph:

Edges: (A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,D,8), (C,E,10), (D,E,2)

Show step-by-step execution with priority queue updates. (8 points)

20. Bellman-Ford Algorithm: Apply Bellman-Ford from vertex A to detect negative cycles in:

Edges: (A,B,1), (A,C,4), (B,C,-3), (B,D,2), (B,E,2), (D,B,1), (D,C,5), (E,D,-3)

Show all relaxation iterations. (6 points)

21. Floyd-Warshall: Compute all-pairs shortest paths for a 4-vertex graph with adjacency matrix:

A B C D
A [ 0 3 ∞ 7]
B [ 8 0 2 ∞]
C [ 5 ∞ 0 1]
D [ 2 ∞ ∞ 0]

Show intermediate matrices D⁽⁰⁾, D⁽¹⁾, D⁽²⁾, D⁽³⁾, D⁽⁴⁾. (5 points)

Section E: Selection and Advanced Concepts (15 points)

22. Random Select: Find the 3rd smallest element in [3, 6, 8, 10, 1, 2, 1] using randomized selection. Show partitioning
steps assuming pivot selections lead to: first partition around 6. (4 points)
23. Union-Find: Perform the following operations on sets {1,2,3,4,5,6,7,8} using weighted union heuristic: Union(1,2),
Union(3,4), Union(5,6), Union(7,8), Union(1,3), Union(5,7), Union(1,5). Show tree structure after each union. (4 points)
24. PageRank: Calculate 2 iterations of PageRank for a 3-page web graph where page A links to B, page B links to C, and
page C links to A. Use damping factor d=0.8. (4 points)

25. Complexity Theory: Classify the following problems as P, NP, or NP-Complete: Shortest Path, Hamiltonian Cycle,
Eulerian Cycle, Boolean Satisfiability (SAT), Matrix Multiplication. Justify your answers. (3 points)
Section F: Multiple Choice Questions (20 points)

Choose the best answer for each question.

26. What is the worst-case time complexity of Quicksort?

• A) O(n log n)
• B) O(n²)
• C) O(n)
• D) O(n³)

27. Which sorting algorithm is NOT stable?

• A) Merge Sort
• B) Insertion Sort
• C) Heap Sort
• D) Bubble Sort

28. What is the time complexity of building a max heap using Build-Max-Heap?

• A) O(n log n)
• B) O(n²)
• C) O(n)
• D) O(log n)

29. Which property is required for a greedy algorithm to work optimally?

• A) Overlapping subproblems only

• B) Optimal substructure only
• C) Both greedy choice property and optimal substructure
• D) Polynomial time complexity

30. What is the time complexity of Dijkstra's algorithm using a binary heap?

• A) O(V²)
• B) O(E log V)
• C) O(V + E)
• D) O(VE)

31. The Bellman-Ford algorithm requires how many iterations to find shortest paths?

• A) |E| - 1
• B) |V| - 1
• C) |V|
• D) |E|

32. What is the space complexity of Merge Sort?

• A) O(1)
• B) O(log n)
• C) O(n)
• D) O(n log n)
33. Which data structure is used in Prim's algorithm for MST?

• A) Stack
• B) Queue
• C) Priority Queue
• D) Hash Table

34. The time complexity of Floyd-Warshall algorithm is:

• A) O(V²)
• B) O(V³)
• C) O(V²E)
• D) O(VE log V)

35. Which algorithm can handle negative edge weights?

• A) Dijkstra's algorithm only

• B) Bellman-Ford algorithm only
• C) Both Dijkstra's and Bellman-Ford
• D) Neither can handle negative weights

Section G: Algorithm Design Problems (40 points)

36. Coin Change Problem (10 points) You are given n types of coins with denominations d₁, d₂, ..., dₙ and need to make
change for amount W using the minimum number of coins. Assume you have unlimited coins of each denomination.

a) Write the recurrence relation for this problem using a DP table. Define what each table entry represents, specify base
cases, and state where the final answer is found. (4 points)

b) Describe a polynomial-time algorithm that finds both the minimum number of coins and which coins to use. (3 points)
c) Analyze the time and space complexity, and provide a correctness argument. (3 points)

37. Edit Distance Problem (10 points) Given two strings X of length m and Y of length n, find the minimum number of
operations (insert, delete, substitute) needed to transform X into Y.

a) Design a DP recurrence relation. Define table entries, base cases, and where to find the optimal solution. Explain each
case in the recurrence. (4 points)

b) Describe how to reconstruct the actual sequence of operations that achieves the minimum edit distance. (3 points)
c) What are the time and space complexities? Prove correctness using optimal substructure. (3 points)

38. Maximum Subarray Problem (10 points) Given an array A of n integers (possibly negative), find the contiguous
subarray with the largest sum.

a) Design a DP solution with recurrence relation. Define what your DP table stores and identify base cases. (4 points)

b) Describe how to find both the maximum sum and the actual subarray indices that achieve it. (3 points)
c) Analyze complexity and prove your solution is correct. Can you solve this in O(1) space? (3 points)

39. Subset Sum Problem (10 points) Given a set of n positive integers S = {s₁, s₂, ..., sₙ} and a target sum T, determine if
there exists a subset of S that sums exactly to T.

a) Formulate this as a DP problem with a boolean table. Define table meaning, recurrence relation, base cases, and where to
find the answer. (4 points)

b) Extend your solution to actually output one such subset if it exists. (3 points)
c) What is the time and space complexity? Is this algorithm polynomial in the input size? Explain. (3 points)
ANSWER KEY:

Section A: Sorting Algorithms

1. Merge Sort [8, 3, 5, 4, 7, 6, 1, 2]:

Divide: [8,3,5,4] [7,6,1,2]

[8,3][5,4] [7,6][1,2]
[8][3][5][4] [7][6][1][2]
Merge: [3,8][4,5] [6,7][1,2]
[3,4,5,8] [1,2,6,7]
[1,2,3,4,5,6,7,8]

2. Quick Sort [6, 10, 13, 5, 8, 3, 2, 11] (pivot=6):

Partition around 6: [3,2,5] 6 [10,13,8,11]

Result: [2,3,5,6,8,10,11,13]

3. Heapsort [4, 10, 3, 5, 1]:

Build Max Heap: [10,5,3,4,1]

Extract: [5,4,3,1] → 10
Extract: [4,1,3] → 5
Extract: [3,1] → 4
Extract: [1] → 3
Final: [1,3,4,5,10]

4. Counting Sort: Count array: [0,2,1,1,1,1,1,1,1], Result: [1,1,2,3,4,5,6,9]

5. Bucket Sort: Distribute into 4 buckets by range [0-0.25), [0.25-0.5), [0.5-0.75), [0.75-1.0), sort each bucket, concatenate.

6. Radix Sort: Sort by ones place, then tens place, then hundreds place.

7. Insertion Sort: [2,5,4,6,1,3] → [2,4,5,6,1,3] → [2,4,5,6,1,3] → [1,2,4,5,6,3] → [1,2,3,4,5,6]

8. Selection Sort always scans remaining elements (n²). Bubble Sort can terminate early if array becomes sorted (best case
O(n)).

Section B: Dynamic Programming

9. Rod Cutting (n=7):

r[0]=0, r[1]=1, r[2]=5, r[3]=8, r[4]=10, r[5]=13, r[6]=17, r[7]=18

Maximum revenue: 18

10. Matrix Chain: Optimal: ((A₁A₂)(A₃A₄)) with cost 405

11. LCS("ABCDGH", "AEDFHR"): LCS = "ADH" with length 3

12. Activity Selection DP: Select activities 0,1,3,4 (maximum 4 activities)

13. Naive recursive: O(2ⁿ), DP: O(n²). DP avoids recomputing same subproblems.

Section C: Greedy Algorithms

14. Huffman Coding:

F(5)+E(9)=14, C(12)+B(13)=25, 14+D(16)=30, 25+30=55, 55+A(45)=100

Codes: A:0, C:100, B:101, D:110, F:1110, E:1111
15. Greedy gives same result: activities 0,1,3,4

16. Kruskal's MST: Select edges in order: (G,H,1), (C,I,2), (F,G,2), (A,B,4), (C,F,4), (C,D,7), (D,E,9)

Section D: Graph Algorithms

17. BFS from A: A→B,C→D,E,F. DFS from A:** A(1,8)→B(2,7)→D(3,4)→E(5,6)→F(finish)

18. Topological Sort: One valid order: socks, undershorts, pants, shoes, watch, shirt, belt, tie, jacket

19. Dijkstra from A: A(0)→C(2)→B(3)→D(8)→E(10)

20. Bellman-Ford: No negative cycle detected. Final distances computed after |V|-1 iterations.

21. Floyd-Warshall: Progressive shortest path matrices through intermediate vertices.

Section E: Advanced Concepts

22. Random Select: Partition around 6, recurse on left partition to find 3rd smallest.

23. Union-Find: Show weighted union trees after each operation.

24. PageRank: Calculate using PR formula with d=0.8 for 2 iterations.

25. Complexity:

• Shortest Path: P
• Hamiltonian Cycle: NP-Complete
• Eulerian Cycle: P
• SAT: NP-Complete
• Matrix Multiplication: P

Section F: Multiple Choice

26. B) O(n²) 27. C) Heap Sort

28. C) O(n) 29. C) Both greedy choice property and optimal substructure 30. B) O(E log V) 31. B) |V| - 1 32. C) O(n) 33. C)
Priority Queue 34. B) O(V³) 35. B) Bellman-Ford algorithm only

Section G: Algorithm Design Problems

36. Coin Change Problem (10 points)

a) Recurrence Relation (4 points):

Let dp[i] = minimum number of coins needed to make amount i

dp[i] = 0 if i = 0 (base case)

dp[i] = ∞ if i < 0 (impossible)

dp[i] = min{dp[i-dⱼ] + 1} for all j where dⱼ ≤ i

• dp[i] represents minimum coins needed for amount i

• Base case: dp[0] = 0 (zero coins for amount 0)
• Final answer: dp[W]

b) Algorithm (3 points):
 1. Initialize dp[0] = 0, dp[i] = ∞ for i > 0
2. For each amount i from 1 to W:
o For each coin denomination dⱼ:
§ If dⱼ ≤ i: dp[i] = min(dp[i], dp[i-dⱼ] + 1)
3. Track parent array to reconstruct solution
4. Return dp[W] and trace back through parent array

c) Complexity & Correctness (3 points):

• Time: O(W×n), Space: O(W)

• Correctness: Optimal substructure - optimal solution for amount i uses optimal solution for amount i-dⱼ
• Each subproblem solved once, building from smaller to larger amounts

37. Edit Distance Problem (10 points)

a) Recurrence Relation (4 points):

Let dp[i][j] = minimum operations to transform X[1..i] to Y[1..j]

dp[i][j] = j if i = 0 (insert j characters)

dp[i][j] = i if j = 0 (delete i characters)

dp[i][j] = dp[i-1][j-1] if X[i] = Y[j] (match)

dp[i][j] = 1 + min{

dp[i-1][j], (delete X[i])

dp[i][j-1], (insert Y[j])

dp[i-1][j-1] (substitute X[i] with Y[j])

} if X[i] ≠ Y[j]

• dp[i][j] represents minimum edit distance between X[1..i] and Y[1..j]

• Final answer: dp[m][n]

b) Reconstruction (3 points): Track which operation was chosen at each dp[i][j]:

• If characters match: move diagonally (no operation)

• If delete was optimal: move up and record delete
• If insert was optimal: move left and record insert
• If substitute was optimal: move diagonally and record substitute Trace back from dp[m][n] to dp[0][0]

c) Complexity & Correctness (3 points):

• Time: O(m×n), Space: O(m×n)

• Optimal substructure: optimal solution contains optimal solutions to subproblems
• Each cell computed once using previously computed values

38. Maximum Subarray Problem (10 points)

a) Recurrence Relation (4 points):

Let dp[i] = maximum sum of subarray ending at position i

dp[i] = A[i] if i = 0 (base case)

dp[i] = max(A[i], dp[i-1] + A[i]) if i > 0

• dp[i] represents maximum sum of any subarray ending exactly at index i

• Final answer: max{dp[i]} for all i
• Alternative: track global maximum while computing
b) Finding Actual Subarray (3 points):

• Track start position when dp[i] = A[i] (new subarray starts)

• Track end position when new global maximum found
• Or use separate arrays to store start/end indices for each dp[i]

c) Complexity & Correctness (3 points):

• Time: O(n), Space: O(n) standard, O(1) optimized (Kadane's algorithm)

• Correctness: At each position, either extend previous subarray or start new one
• Optimal substructure: optimal subarray ending at i uses optimal solution for position i-1
• O(1) space: only need previous dp value, not entire array

39. Subset Sum Problem (10 points)

a) Recurrence Relation (4 points):

Let dp[i][j] = true if subset of first i elements can sum to j

dp[i][j] = true if j = 0 (empty subset sums to 0)

dp[i][j] = false if i = 0 and j > 0 (no elements, positive sum)

dp[i][j] = dp[i-1][j] OR dp[i-1][j-sᵢ] if i > 0 and sᵢ ≤ j

dp[i][j] = dp[i-1][j] if i > 0 and sᵢ > j

• dp[i][j] = true if we can achieve sum j using first i elements

• Base cases: dp[i][0] = true for all i, dp[0][j] = false for j > 0
• Final answer: dp[n][T]

b) Reconstructing Subset (3 points): If dp[n][T] = true, trace back:

• If dp[i][j] came from dp[i-1][j]: element i not included

• If dp[i][j] came from dp[i-1][j-sᵢ]: element i included Start from dp[n][T] and work backwards to build subset

c) Complexity Analysis (3 points):

• Time: O(n×T), Space: O(n×T)

• This is NOT polynomial in input size! Input size is O(n + log T), but algorithm is O(n×T)
• This is "pseudo-polynomial" - polynomial in numeric value of T, not its representation
• If T is exponential in input size, algorithm becomes exponential

Total: 160 points Grade Scale: A: 144-160, B: 128-143, C: 112-127, D: 96-111, F: <96