PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 2

T(n) = 2T(√n) + 1
Put n = 2^K
T(2^K) = 2T(2^K/2) + 1
T(2^K) = δ(K)

By master's theorem
δ(K) = θ(K)
T(2^K) = θ(K)
T(n) = θ(log n) ∵ 2^K = n

47 If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)²] equals _____

Using Linearity of Expectation, we can write,
E[(X+2)²] = E[X²] + E[4X] + E[4]
The Poisson distribution, mean and variance are same. Here Mean is given as 5. So variance should also be 5.
Also,
Variance = E[X²] – (E[X])²
5 = E[X²] – 25.
E[X²] = 30
Thus E[(X+2)²] = 30 + 4*5 + 4 = 54.

48 Consider the following C function

(int fun (int n) {
int i, j;
for (i = 1; i < = n; i++) {
for (j = 1; j < n ; j+=i) {
printf (“%d %d, i, j ) ;
}
}
})
Time complexity of fun in terms of θ notation is

for i = 1
j will run from 1 to n by incrementing by '1' in each step 'j 'will run for n times
For i=2
j will run from 1 to n by incrementing by ‘2’ in each step j will run for n/2 times

next time j will run for n/3 times
and so on

time complexity = n + n/2 + n/3 + n/4 + .....
= n(1+1/2+1/3+.....)
=nlogn

49 The pre-order transversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

Given: Preorder ! 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20
In order! 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
Note: BST In order will give ascending order
Corresponding BST is

∴ Post order is 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12

50 Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x, y, q and r are all unsigned int.
(while (r >= y) {
r = r – y;
q = q +1;
})
Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y * q + r)?

Given, program is:
(while (r y){
}
If we want to final value as Then initial value of r should be equal to x (Since y is subtracted from r each time in given code). q incremented by 1 (q is quotient here). To avoid undefined behavior, value of y should be greater than zero. Therefore, (q == 0)&&(r == x)&&(y > 0))