UGC NET CSE | June 2016 | Part 3 | Question: 34

Question

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}$

$\textbf{Codes :}$

• A. $\text{(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)}$
• B. $\text{(a)-(i), (b)-(iv), (c)-((ii), (d)-(iii)}$
• C. $\text{(a)-(iii), (b)-(ii), (c)-(iv), (d)-(i)}$
• D. $\text{(a)-(iii), (b)-(iv), (c)-(ii), (d)-(i)}$

Answer 1

(a) Huffman codes : θ(n) 

(b) Optimal polygon triangulation : θ(n³)

(c) Activity selection problem : O(n log n)

(d) Quick sort : O(n²) 

Time complexity of the Huffman algorithm is O(n Logn). If we know that the given array is sorted (by non-decreasing order of frequency), but we can generate Huffman codes in O(n) time. 

http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding-set-2/

Comments

This answer is in correct

option 3 is correct

---

(c) Activity selection problem : O(n log n)

http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

(a) Huffman codes : θ(n) 

http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding-set-2/

but here no option matching so choose close one

Answer 2

Ans: None of the above or there is a typing mistake in above question

The question should be like this:

Match the following:

a. Huffman code	i. O(n^2)
b. Optical Polygon Triangulation	ii. θ(n^3)
c. Activity selection problem	iii. O(nlgn)
d. Quicksort	iv. θ(n)

1. a-i, b-ii, c-iv, d-iii
2. a-i, b-iv, c-ii, d-iii
3. a-iii, b-ii, c-iv, d-i
4. a-iii, b-iv, c-ii, d-i

So the correct ans would be: 

Huffman code	O(nlgn)
Optical Polygon Triangulation	O(n^3)
Activity selection problem	θ(n)
Quicksort	O(n^2)

Ans: 3

ref: http://www.utdallas.edu/~daescu/polygon-triangulation.pdf