Question 1

Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?

A : G1 = (V,E1) where E1 = { (u,v) | (u,v) ∉ E }
B : G2 = (V,E2) where E2 = { (u,v) | (v,u) ∈ E }
C : G3 = (V,E3) where E1 = { (u,v) | there is a path of length <=2 from
D : G4 = (V4,E) where V4 is the set of vertices in G which are not isol


     Correct answer is :B

  •   Question 2

    Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

    A : θ (n)
    B : θ (n+m)
    C : θ (n2)
    D : θ (m2)


     Correct answer is :C

     Solution :
      DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V2)

  •   Question 3

    Consider the directed graph given below.
    Which one of the following is TRUE?
    Note: Edge is from R to Q

    A : The graph does not have any topological ordering
    B : Both PQRS and SRQP are topological orderings
    C : Both PSRQ and SPRQ are topological orderings.
    D : PSRQ is the only topological ordering.


     Correct answer is :C

     Solution :
      Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Topological ordering is possible iff graph has no directed cycles.
    (A) As the given graph doesnt contain any directed cycles, it has at least one topological ordering. So option (A) is false
    (B) PQRS cannot be topological ordering because S should come before R in the ordering as there is a directed edge from S to R and Q

  •   Question 4

    Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

    A : t1=5
    B : t1 < t2
    C : t1 > t2
    D : t1 = t2


     Correct answer is :C

     Solution :
      Partition algorithm for quick sort
    Partition (A,P,q) //A [P,.....]
    x <- A [P[ // pivot A= [P]
    i <-P
    for j= P + 1 to q
    do if A [j] <= x
    then i <- i + 1
    exchange A [i] <-> A [j]
    exchange A [P] <-> A [i]
    return i [returning where pivot element is there after partitioning]
    Recursively call the above algorithm for the two sub arrays [elements before and after pivot element] to complete the sorting.

  •   Question 5

    The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.


     Correct answer is :148

     Solution :
      To find minimum and maximum element out of n numbers, we need to have at least (3n/2-2) comparisons.

  •   Question 6

    Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

    A : 3,0 and 1
    B : 3,3 and 3
    C : 4,0 and 1
    D : 3,0 and 2


     Correct answer is :A

     Solution :
      Maximum&minimum chain lengths are 3&0 respectively
    Average chain length = 0+3+1+1+0+1+2+0+1/9 = 1

  •   Question 7

    Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {i, f): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a,b) and (c,d) if |a - c| <= 1 and |b - d| <= 1 The number of edges in the graph is _____________.


     Correct answer is :506

     Solution :
      The graph formed by the description contains 4 vertices of degree 3 and 40verices of degree 5 and 100 vertices of degree 8.
    According to sum of the degrees theorem 4*3+40*5+100*8 = 2|E|
    |E| = 1012/2 = 506

  •   Question 8

    Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
    T(n) = | 2T(n/2) + log n

    A : θ (n)
    B : θ (nlog n)
    C : θ (n2)
    D : θ (log n)


     Correct answer is :A

  •   Question 9

    Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

    A : the shortest path between every pair of vertices.
    B : the shortest path from W to every vertex in the graph.
    C : the shortest paths from W to only those nodes that are leaves of T.
    D : the longest path in the graph.


     Correct answer is :B

     Solution :
      One of the application of BFS algorithm is to find the shortest path between nodes u and v. But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from w to every vertex of the graph

  •   Question 10

    Consider two strings A "= q pqrr " 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 = ___.


     Correct answer is :34

     Solution :
      Given is
    A = qpqrr
    B = pqprqrp
    The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:
    (1) qpqr
    (2) pqrr
    (3) qprr
    So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34.

  •   Question 11

    The number of distinct minimum spanning trees for the weighted graph below is


     Correct answer is :6

  •   Question 12

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


     Correct answer is :19

  •   Question 13

    You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

    A : O(n2)
    B : O(n logn)
    C : θ(n logn)
    D : O(n3)


     Correct answer is :A

     Solution :
      The Worst case time complexity of quick sort is O (n2). The central element is chosen as the pivot and not the median so that central element could be an extreme in the final array every time.

  •   Question 14

    Which of the following statements are CORRECT?
    1)Static allocation of all data areas by a compiler makes it impossible to implement recursion.
    2)Automatic garbage collection is essential to implement recursion.
    3)Dynamic allocation of activation records is essential to implement recursion.
    4)Both heap and stack are essential to implement recursion.

    A : 1 and 2 only
    B : 2 and 3 only
    C : 3 and 4 only
    D : 1 and 3 only


     Correct answer is :D

     Solution :
      To implement recursion, activation record should be implemented by providing dynamic memory allocation. This dynamic allocation is done from runtime stack. Heap is essential to allocate memory for data structures at run-time, not for recursion.
    So statement 1 and 3 are correct.

  •   Question 15

    Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is _____.


     Correct answer is :150

     Solution :
      By definition, T(9) = Dist. From 9 to 100
    As given, T(9) = 1+min (T(y), T()z) = 1+min (Dist. from y to 100, Dist. From z to 100)
    1=Dist. from 9 to y/Dist. From 9 to z 
    There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15. 
    Therefore, y and z are 10 and 15 (in any order) 
    Product yz = 150. Answ

  •   Question 16

    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( na logb n + mc logd n , the value of a + 10b + 100c + 1000d is _______.


     Correct answer is :110

     Solution :
      It takes (log n ) time to determine numbers n1 and n2 in balanced binary search tree T such that
    1. n1 is the smallest number greater than or equal to L and there is no predecessor n1 of n1 such that n1 is equal to n1.
    2. n2 is the largest number less than or equal to H and there is no successor of n2 of n2 such that is equal to n2.
    Since there are m elements between n1 and n2, it takes m time to add all elements between n1 and n2.
    So time complexity is O (log n + m)

  •   Question 17

    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?

    A : (97 97 97)/1003
    B : (99 98 97)/1003
    C : (97 96 95)/1003
    D : (97 96 95)/(3! 1003)


     Correct answer is :A

  •   Question 18

    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 1, j, k;
    i = 0;
    j = n 1;
    do { k = (i + j) /2;
    if (x < = listA [k]) j = k 1;
    If (listA [k] < = x) i = k+1;
    while (1 < = j);
    If (listA [k] = = x)
    return (k) ;
    else return -1;
    Which one of the following statements about the function ProcessArray is CORRECT?

    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.


     Correct answer is :B

     Solution :
      By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D.
    A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is

    TOTAL = 18
    CORRECT / TOTAL = /18