Match the following with respect to algorithm paradigms (Design Techniques):…
2018
Match the following with respect to algorithm paradigms (Design Techniques):
List–I
(a) The 8-Queen’s Problem
(b) Single-source shortest path
(c) STRASSEN’s Matrix
(d) Optimal binary search trees
List–II
(i) Dynamic Programming
(ii) Divide and Conquer
(iii) Greedy approach
(iv) Backtracking
- A.
(a) – (iv), (b) – (i), (c) – (iii), (d) – (ii)
- B.
(a) – (iv), (b) – (iii), (c) – (i), (d) – (ii)
- C.
(a) – (iii), (b) – (iv), (c) – (ii), (d) – (i)
- D.
(a) – (iv), (b) – (iii), (c) – (ii), (d) – (i)
Attempted by 17 students.
Show answer & explanation
Correct answer: D
(a) The 8-Queen’s Problem → (iv) Backtracking
→ Tries all possibilities and backtracks on invalid placements.
(b) Single-source shortest path → (iii) Greedy approach
→ Algorithms like Dijkstra choose the locally optimal edge at each step.
(c) STRASSEN’s Matrix → (ii) Divide and Conquer
→ Matrix is divided into sub-matrices and solved recursively.
(d) Optimal binary search trees → (i) Dynamic Programming
→ Uses optimal substructure and overlapping subproblems.
A video solution is available for this question — log in and enroll to watch it.