# ALGORITHMS |Gate-2004| Previous Year Questions| Set-12 ALGORITHMS |Gate-2004|

1. An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n – 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n – 1)/2⌋, ⌊(n – 3)/2⌋, ….., 0. The time required to construct a heap in this manner is : [GATE – 2004]

a. O(log n)
b. O(n)
c. O(n log log n)
d. O(n log n)

2. Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE? [GATE – 2004]

a. f(n) + g(n) = O(h(n)) + h(n))
b. f(n) = O(h(n))
c. fh(n) ≠ O(f(n))
d. f(n)h(n) ≠ O(g(n)h(n))

3. Consider the undirected graph below: Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree? [GATE – 2004]

a.(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
b. (A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
c. (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
d. (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)

4. Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. [GATE – 2004]

a. P-II, Q-III, R-IV, S-I
b. P-IV, Q-III, R-I, S-II
c. P-III, Q-II, R-IV, S-I
d. P-IV, Q-II, R-I, S-III