Match the following with respect to algorithm paradigms :…
2017
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}\)
\(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 95 students.
Show answer & explanation
Correct answer: D
Correct matching: Merge sort → Divide and conquer; Huffman coding → Greedy approach; Optimal polygon triangulation → Dynamic programming; Subset sum problem → Backtracking.
Merge sort: Divide and conquer — the algorithm divides the array into halves, recursively sorts each half, and then merges the results.
Huffman coding: Greedy approach — repeatedly combine the two least frequent symbols to build an optimal prefix code; each local greedy choice leads to a global optimum.
Optimal polygon triangulation: Dynamic programming — use optimal substructure over polygon chains (choose a vertex to form a triangle and combine optimal solutions of subpolygons).
Subset sum problem: Backtracking — search over subsets (include/exclude choices) to find a subset with the target sum. (Note: there is also a standard dynamic programming pseudo-polynomial solution, but the straightforward search classification is backtracking.)