# Divide and conquer: GATE CS question with solution

From the GATE Daily set of 26 October 2026, question 7 of 10 (https://gatedaily.in/q/2026-10-26-match-algorithms-to-design-paradigms/). Difficulty: easy.

### Q.7 · Algorithms · Divide and conquer · MCQ, 1 mark (choose one option)

Match each algorithm in List-I with the design paradigm in List-II that it follows.

| List-I | List-II |
|---|---|
| (P) Bellman-Ford algorithm for single-source shortest paths | (i) Divide and conquer |
| (Q) Kruskal's algorithm for a minimum spanning tree | (ii) Dynamic programming |
| (R) Strassen's matrix multiplication | (iii) Greedy method |
| (S) Solving the N-Queens problem by placing queens one column at a time and undoing a placement when no safe square remains | (iv) Backtracking |

(A) P-iii, Q-ii, R-i, S-iv
(B) P-ii, Q-iii, R-i, S-iv
(C) P-ii, Q-iii, R-iv, S-i
(D) P-ii, Q-ii, R-i, S-iv

**Answer:** (B) P-ii, Q-iii, R-i, S-iv

**Solution.** **Method: name the paradigm of each algorithm, then eliminate options.**

- **Bellman-Ford** computes $d_k(v)$, the shortest distance to $v$ using at most $k$ edges, from $d_{k-1}$ for $k = 1, \dots, |V|-1$. Building answers from smaller subproblems in a fixed order is **dynamic programming** (ii).
- **Kruskal** repeatedly adds the cheapest edge that does not form a cycle and never reconsiders it: **greedy** (iii).
- **Strassen** splits each matrix into four quadrants, makes 7 recursive multiplications and combines them: **divide and conquer** (i).
- **N-Queens** with "place, and undo when stuck" is **backtracking** (iv).

So P-ii, Q-iii, R-i, S-iv.

**Trap.** Shortest-path algorithms are not all greedy: Dijkstra is greedy, but Bellman-Ford and Floyd-Warshall are dynamic programming.

**What was tested:** the textbook paradigm behind standard algorithms.

**Remember:** Dijkstra, Prim, Kruskal and Huffman are greedy; Bellman-Ford and Floyd-Warshall are dynamic programming; mergesort, quicksort, binary search and Strassen are divide and conquer.

**Why each option:**
- (A) Swaps P and Q: Bellman-Ford is not greedy (that is Dijkstra) and Kruskal is not dynamic programming.
- (B) Bellman-Ford is DP over path length, Kruskal is greedy, Strassen is divide and conquer, N-Queens is backtracking.
- (C) Strassen splits matrices into quadrants and recurses, which is divide and conquer, not backtracking.
- (D) Kruskal never revisits a decision or combines subproblem tables; it greedily takes the cheapest safe edge.