ALGORITHMS |Gate-2017|
1. Consider the following functions from positives integers to real numbers
10,√n,n, log2n, 100/n
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is: [GATE -2017]
a. log2n,100/n,10, √n,n
b. 100/n,10, log2n, √n,n
c. 10, 100/n, √n, log2n,n
d. 100/n, log2n,10, √n,n
Answer : b)
2. Consider the following table : [GATE -2017]
| Algorithms | Design Paradigms |
| (P)Kruskal | (i) divide and conquer |
| (Q)Quicksort | (ii) Greedy |
| (R)floyd-warshall | (iii) Dynamic Programming |
Match the algorithm to design paradigms they are based on:
a. (P)↔(ii), Q↔(iii), (R)↔(i)
b. (P)↔(iii), Q↔(i), (R)↔(ii)
c. (P)↔(ii), Q↔(i), (R)↔(iii)
d. (P)↔(i), Q↔(ii), (R)↔(iii)
Answer : c)
ALGORITHMS |Gate-2017|
3. Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true? [GATE – 2017]
a. (I) only
b. (II) only
c. both (I) and (II
d. neither (I) nor (II)
Answer : a)
4. Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________. [GATE – 2017]
a. 5
b. 6
c. 7
d. 8
Answer : a)
ALGORITHMS |Gate-2017|
5. Match the algorithms with their time complexities: [GATE – 2017]
Algorithm Time complexity
(P) Towers of Hanoi with n disks (i) Θ(n2)
(Q) Binary search given n stored numbers (ii) Θ(n log n)
(R) Heap sort given n numbers at the worst case (iii) Θ(2n)
(S) Addition of two n×n matrices (iv) Θ(log n)
a. P→(iii), Q→(iv), R→(i), S→(ii)
b. P→(iv), Q→(iii), R→(i), S→(ii)
c. P→(iii), Q→(iv), R→(ii), S→(i
d. P→(iv), Q→(iii), R→(ii), S→(i)
Answer : c)
6. Consider the recurrence function
Then T(n) in terms of Θ notation is : [GATE – 2017]
a. Θ(loglogn)
b. Θ(logn)
c. Θ(√n)
d. Θ(n)]
Answer : b)
7. Consider the following C function. [GATE – 2017]
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
a. Θ(n√n)
b. Θ(n2 )
c. (n logn)
d. Θ(n2 logn)
Answer : c)
8. A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:
| Character | Probability |
| P | 0.22 |
| Q | 0.34 |
| R | 0.17 |
| S | 0.19 |
| T | 0.08 |
| Total | 1.00 |
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________. [GATE – 2017]
a. 225
b. 226
c. 227
d. 228
Answer : a)
OS – GATE Previous Year Questions
DS – GATE Previous Year Questions