**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. Θ(n^{2})

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(n^{2})

b. O(n log n)

c. Θ(n logn)

d. O(n^{3})

*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(n^{a}log^{b}n + m^{c}log^{d}n), 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)/100^{3}

b. (97×96×95)/100^{3}

c. (97×97×97)/100^{3}

d. (97×96×95)/(3!×100^{3})

*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)*