# ALGORITHMS |Gate-2014| Previous Year Questions| Set-7 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

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. 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

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. Θ(log⁡n)

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

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

7. The number of distinct minimum spanning trees for the weighted graph below is ____  [GATE – 2014]

a. 6
b. 7
c. 8
d. 9

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

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

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 log⁡n)
d. O(n3)

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

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)

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.

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.