Q.7
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 |
One try. It counts in your 26 Oct 2026 set.
Show solution
RememberDijkstra, Prim, Kruskal and Huffman are greedy; Bellman-Ford and Floyd-Warshall are dynamic programming; mergesort, quicksort, binary search and Strassen are divide and conquer.
Solution MCQ · 1 mark · −⅓ if wrong
Answer: (B) P-ii, Q-iii, R-i, S-iv
Method: name the paradigm of each algorithm, then eliminate options.
- Bellman-Ford computes , the shortest distance to using at most edges, from for . 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.
Copied. Paste it into the new chat.Too long to send. Copy the question and solution by hand.