July2016 cs Q34
| (a) Huffman codes | (i) O(n2) |
| (b) Optimal polygon triangulation | (ii) θ(n3) |
| (c) Activity selection problem | (iii) O(nlgn) |
| (d) Quicksort | (iv) θ(n) |
Codes:
| (a) | (b) | (c) | (d) | |
| (1) | (i) | (ii) | (iv) | (iii) |
| (2) | (i) | (iv) | (ii) | (iii) |
| (3) | (iii) | (ii) | (iv) | (i) |
| (4) | (iii) | (iv) | (ii) | (i) |
- Option : C
- Explanation :
- Huffman codes takes O(nlgn) time.
- Optimal polygon triangulation takes θ(n3) time
- Activity selection problem takes θ(n) time
- Quicksort takes O(n2) time
