Match the following : \(\begin{array}{clcl} \text{(a)} & \text{Huffman Code} &…
2016
Match the following :
\(\begin{array}{clcl} \text{(a)} & \text{Huffman Code} & \text{(i)} & O(n^2) \\ \text{(b)} & \text{Optical Polygon Triangulation} & \text{(ii)} & \theta(n^2) \\ \text{(c)} & \text{Activity Selection Problem} & \text{(iii)} & O(n\lg n) \\ \text{(d)} & \text{Quicksort} & \text{(iv)} & \theta(n) \\ \end{array}\)
Codes :
- A.
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
- B.
(a)-(i), (b)-(iv), (c)-((ii), (d)-(iii)
- C.
(a)-(iii), (b)-(ii), (c)-(iv), (d)-(i)
- D.
(a)-(iii), (b)-(iv), (c)-(ii), (d)-(i)
Attempted by 326 students.
Show answer & explanation
Correct answer: C
Correct matching and brief reasons:
Huffman Code → O(n log n). Reason: Building the Huffman tree with a priority queue repeatedly extracts and inserts nodes, leading to O(n log n) time.
Optimal polygon triangulation → Θ(n^2). Reason: A common simple triangulation algorithm (ear clipping) runs in Θ(n^2) time for an n-vertex polygon.
Activity selection problem → Θ(n). Reason: After sorting activities by finish time, the greedy selection scans once to pick compatible activities, which is linear time.
Quicksort → O(n^2). Reason: Quicksort has average-case O(n log n) but its worst-case running time is O(n^2), which is the intended complexity here.