The Exam Blueprint: Module 2 PYQ Deep Analysis (2022–2024)

An analysis of 21 exam questions spanning 2022 to 2024 reveals that Module 2 is the core application module of the course. It heavily emphasizes Dynamic Programming (MCM), Greedy Algorithms (Knapsack/Huffman), and Backtracking/Branch-and-Bound traces. You must be prepared to trace large matrices and state-space trees.

Complete PYQ Table (21 Questions)

Total marks tracked: 129 marks across 3 years.

---

Topic Heat Map

---

The Guaranteed Question Types

1. 🔴 Dynamic Programming: Matrix Chain Multiplication (7–14M) Appeared in 2022 and 2023. You must construct the $m$ (cost) and $s$ (split) tables. The 2023 paper asked a massive 14-mark version with 5 matrices.

2. 🔴 Greedy Algorithms: Fractional Knapsack or Huffman (7M) Highly predictable. Sort items by profit/weight ratio for Knapsack, or build the min-heap tree for Huffman coding.

3. 🟠 Backtracking / Branch-and-Bound Traces (7–10M) Drawing the state-space tree is mandatory. Problems rotate between Graph Coloring, Hamiltonian Cycle, N-Queens, and TSP.

4. 🟡 Quick Sort (7–9M) Frequently asked to trace the partition steps and explicitly define the best/worst/average case time complexities.

Solved Numericals: The Exam-Critical Calculations

---

Numerical 1: Matrix Chain Multiplication (DP)

"Find minimum operations for matrix chain: A(10×20), B(20×50), C(50×1), D(1×100)."

Dimension array $P$: $P = [10, 20, 50, 1, 100]$ (Number of matrices $n=4$)

Formula: $m[i, j] = \min_{i \le k < j} \{ m[i, k] + m[k+1, j] + P_{i-1} P_k P_j \}$

Step 1: Chain length = 1 $m[1,1] = m[2,2] = m[3,3] = m[4,4] = 0$

Step 2: Chain length = 2 $m[1,2] = m[1,1] + m[2,2] + 10 \times 20 \times 50 = 10,000$ (Split $k=1$) $m[2,3] = m[2,2] + m[3,3] + 20 \times 50 \times 1 = 1,000$ (Split $k=2$) $m[3,4] = m[3,3] + m[4,4] + 50 \times 1 \times 100 = 5,000$ (Split $k=3$)

Step 3: Chain length = 3 $m[1,3] = \min \begin{cases} k=1: m[1,1] + m[2,3] + 10 \times 20 \times 1 = 0 + 1000 + 200 = \mathbf{1,200} \\ k=2: m[1,2] + m[3,3] + 10 \times 50 \times 1 = 10000 + 0 + 500 = 10,500 \end{cases}$ Optimal split for $m[1,3]$ is $k=1$.

$m[2,4] = \min \begin{cases} k=2: m[2,2] + m[3,4] + 20 \times 50 \times 100 = 0 + 5000 + 100,000 = 105,000 \\ k=3: m[2,3] + m[4,4] + 20 \times 1 \times 100 = 1000 + 0 + 2000 = \mathbf{3,000} \end{cases}$ Optimal split for $m[2,4]$ is $k=3$.

Step 4: Chain length = 4 $m[1,4] = \min \begin{cases} k=1: m[1,1] + m[2,4] + 10 \times 20 \times 100 = 0 + 3000 + 20000 = 23,000 \\ k=2: m[1,2] + m[3,4] + 10 \times 50 \times 100 = 10000 + 5000 + 50000 = 65,000 \\ k=3: m[1,3] + m[4,4] + 10 \times 1 \times 100 = 1200 + 0 + 1000 = \mathbf{2,200} \end{cases}$

Result: The minimum number of multiplications is 2,200. Optimal Parenthesization: Using the $k$ values, the split for 1..4 is at 3, so (A..C)(D). For 1..3 the split is at 1, so (A)(BC). Final result: ( A ( B C ) ) D. Complexity: $O(n^3)$ time and $O(n^2)$ space.

---

Numerical 2: Fractional Knapsack (Greedy)

"Capacity W=15. Objects (Profit, Weight): (5,1), (10,3), (15,5), (7,4), (8,1), (9,3), (4,2). Find max profit."

Step 1: Calculate Profit/Weight ratios ($P/W$) and Sort descending

Step 2: Add to knapsack (Capacity = 15)

1. Take Item 5 (Wt 1). Remaining = 14. Profit = 8.
2. Take Item 1 (Wt 1). Remaining = 13. Profit = 8 + 5 = 13.
3. Take Item 2 (Wt 3). Remaining = 10. Profit = 13 + 10 = 23.
4. Take Item 3 (Wt 5). Remaining = 5. Profit = 23 + 15 = 38.
5. Take Item 6 (Wt 3). Remaining = 2. Profit = 38 + 9 = 47.
6. Take Item 7 (Wt 2). Remaining = 0. Profit = 47 + 4 = 51.

Result: The knapsack is exactly full (15 units) without needing a fraction of any item. Total max profit is 51. Item 4 is left behind.

High-Yield Subjective Bank: Structure Your Answers

---

####Differentiate Divide & Conquer, Greedy, and Dynamic Programming (7 Marks)**

Answer structure (Table Format):

---

####Differentiate Backtracking and Branch & Bound (4 Marks)**

Answer structure:

1. Goal:
   • Backtracking is used to find all possible solutions (e.g., all arrangements of N-Queens) or any satisfying solution.
   • Branch & Bound is used strictly to find the optimal (minimum or maximum) solution (e.g., shortest TSP route).
2. Traversal Method:
   • Backtracking uses Depth-First Search (DFS).
   • Branch & Bound typically uses Breadth-First Search (BFS) or Best-First Search (using a priority queue).
3. Pruning Mechanism:
   • Backtracking prunes the tree when the current state violates constraints (bounding function).
   • Branch & Bound calculates a bound (e.g., lower bound cost) at each node. If a node's bound is worse than the best solution found so far, the entire branch is pruned.
4. Applicability:
   • Backtracking: Graph coloring, N-Queens, Sudoku.
   • Branch & Bound: TSP, 0/1 Knapsack optimization.

---

####Why Greedy Fails for 0/1 Knapsack (Part of 7 Marks)**

Answer structure:

1. The Greedy Property: A greedy algorithm assumes that taking the item with the highest Profit/Weight ratio will lead to the global maximum.
2. The 0/1 Constraint: Unlike Fractional Knapsack, you cannot take a fraction of an item. You either take the whole item (1) or leave it (0).
3. The Failure Case:
   • Capacity $W = 50$.
   • Item 1: Profit = 60, Weight = 10 ($P/W = 6$).
   • Item 2: Profit = 100, Weight = 20 ($P/W = 5$).
   • Item 3: Profit = 120, Weight = 30 ($P/W = 4$).
   • Greedy approach: Picks Item 1 first (best ratio). Remaining weight = 40. Then picks Item 2. Remaining weight = 20. Cannot fit Item 3. Total Profit = 160.
   • Optimal (DP) approach: Pick Item 2 and Item 3. Total weight = 50 (fits perfectly). Total Profit = 220.
4. Conclusion: Because taking a high-ratio item might leave empty, unusable space in the knapsack, the greedy choice does not guarantee optimal substructure for the 0/1 variant. Dynamic Programming must be used to evaluate all combinations.