Match the following with respect to algorithm paradigms :…
2018
Match the following with respect to algorithm paradigms :
\(\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{(a)} & \text{Merge sort} & \text{(i)} & \text{Dynamic programming} \\ \text{(b)} & \text{Huffman coding} & \text{(ii)} & \text{Greedy approach} \\ \text{(c)} & \text{Optimal polygon triangulation} & \text{(iii)} & \text{Divide and conquer} \\ \text{(d)} & \text{Subset sum problem} & \text{(iv)} & \text{Back tracking} \\ \end{array}\)
\(\textbf{Codes :}\)
- A.
(a))-(iii), (b)-(i), (c)-(ii), (d)-(iv)
- B.
(a)-(ii), (b)-(i), (c)-(iv), (d)-(iii)
- C.
(a)-(ii), (b)-(i), (c)-(iii), (d)-(iv)
- D.
(a)-(iii), (b)-(ii), (c)-(i), (d)-(iv)
Attempted by 106 students.
Show answer & explanation
Correct answer: D
Correct matching:
Merge sort — Divide and conquer: Merge sort recursively splits the array into halves, sorts each half, and then merges the sorted halves.
Huffman coding — Greedy approach: Huffman coding builds the optimal prefix tree by repeatedly making locally optimal (greedy) merges of the least-weight nodes.
Optimal polygon triangulation — Dynamic programming: The problem is solved by combining optimal triangulations of subpolygons and using stored subproblem results to build the overall optimum.
Subset sum problem — Back tracking: A straightforward approach is to explore subsets (backtracking/exhaustive search) to find a subset that sums to the target.
Note: Subset sum also has a Dynamic programming solution (pseudo-polynomial time) for the decision/version that demonstrates an alternative paradigm; in this matching it is paired with Back tracking.