ALGORITHMS |Gate-2014|
1. There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______. [GATE – 2014]
a. 12
b. 13
c. 14
d. 15
Answer: a)
2. Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)? [GATE – 2014]
a.
b.
c.
d.
Answer : d)
3. The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________. [GATE – 2014]
a. 148
b. 149
c. 150
d. 151
Answer : a)
4. Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? [GATE – 2014]
T(n) = 2T(n/2) + Logn
a. Θ(n)
b. Θ(nlog n)
c. Θ(n2)
d. Θ(logn)
Answer : a)
5. Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x+10y = _________. [GATE – 2014]
a. 36
b. 35
c. 34
d. 37
Answer : c)
6. Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ______. [GATE – 2014]
a. 358
b. 360
c. 361
d. 362
Answer : a)
7. The number of distinct minimum spanning trees for the weighted graph below is ____ [GATE – 2014]
a. 6
b. 7
c. 8
d. 9
Answer : a)
8. Consider the following rooted tree with the vertex la beled P as t he root: The order in which the nodes are visited during an i n-order trave rsal of the tree is : [GATE – 2014]
a. SQPTRWUV
b. SQPTWUVR
c. SQPTUWRV
d. SQPTRUWV
Answer : a)
9. Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________. [GATE – 2014]
a. 22
b. 20
c. 21
d. 19
Answer : d)
ALGORITHMS |Gate-2014|
10. You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is : [GATE – 2014]
a. O(n2)
b. O(n log n)
c. Θ(n logn)
d. O(n3)
Answer : a)
11. Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____. [GATE – 2014]
a. 111
b. 110
c. 112
d. 113
Answer : b)
ALGORITHMS |Gate-2014|
12. Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions? [GATE – 2014]
a. (99×98×97)/1003
b. (97×96×95)/1003
c. (97×97×97)/1003
d. (97×96×95)/(3!×1003)
Answer : c)
ALGORITHMS |Gate-2014|
13. Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the : [GATE – 2014]
a. number of internal nodes in the tree.
b. number of nodes without a right sibling in the tree.
c. height of the tree.
d. number of leaf nodes in the tree.
Answer : d)
14. Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; }while (i <= j); if (listA[k] == x) return(k); else return -1; } Which one of the following statements about the function ProcessArray is CORRECT? [GATE – 2014]
a. It will run into an infinite loop when x is not in listA.
b. It is an implementation of binary search.
c. It will always find the maximum element in listA.
d. It will return −1 even when x is present in listA.
Answer : b)