Loading

SET 5


  Question 1

Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?



A : 1 2 3 4 5 6
B : 1 3 2 4 5 6
C : 1 3 2 4 6 5
D : 3 2 4 1 6 5


  •  
    .

     Correct answer is :D

     Solution :
      1 appears after 2 and 3 which is not possible in Topological Sorting.

  •   Question 2

    Which of the following sorting algorithms has the lowest worst-case complexity?

    A : Merge sort
    B : Bubble sort
    C : Quick sort
    D : Selection sort


  •  
    .

     Correct answer is :A

     Solution :
      Worst case complexities for the above sorting algorithms are as follows:
    Merge Sort - nLogn
    Bubble Sort - n^2
    Quick Sort - n^2
    Selection Sort - n^2

  •   Question 3

    Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

    A : 8, _, _, _, _, _, 10
    B : 1, 8, 10, _, _, _, 3
    C : 1, _, _, _, _, _,3
    D : 1, 10, 8, _, _, _, 3


  •  
    .

     Correct answer is :B

     Solution :
      Let us put values 1, 3, 8, 10 in the hash of size 7.
    Initially, hash table is empty

    - - - - - - -
    0 1 2 3 4 5 6
    The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0

    1 - - - - - -
    0 1 2 3 4 5 6
    The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6

    1 - - - - - 3
    0 1 2 3 4 5 6
    The value o

  •   Question 4

    In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

    A : Dijkstra’s algorithm starting from S
    B : Warshall’s algorithm
    C : Performing a DFS starting from S
    D : Performing a BFS starting from S


  •  
    .

     Correct answer is :D

     Solution :
      * Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)
    * Time Comlexity of the Warshall’s algorithm is O(|V|^3)
    * DFS cannot be used for finding shortest paths
    * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

  •   Question 5

    In the following C function, let n >= m.
    int gcd(n,m)
    {
    if (n%m ==0) return m;
    n = n%m;
    return gcd(m,n);
    }
    How many recursive calls are made by this function?


    A : θ (n)
    B : ω(n)
    C : θ (loglogn)
    D : θ (sqrt(n))


  •  
    .

     Correct answer is :A

     Solution :
      Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).

  •   Question 6

    What is the time complexity of the following recursive function:
    int DoSomething (int n)
    {
    if (n <= 2)
    return 1;
    else
    return (DoSomething (floor(sqrt(n))) + n);
    }


    A : θ (n)
    B : θ (n log n)
    C : θ (logn)
    D : θ (loglog n)


  •  
    .

     Correct answer is :D

     Solution :
      Recursive relation for the DoSomething() is
    T(n) = T(√n) + C1 if n > 2
    We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.
    Let n = 2^m, T(n) = T(2^m)
    Let T(2^m) = S(m)
    From the above two, T(n) = S(m)
    S(m) = S(m/2) + C1 /* This is simply binary search recursion*/
    S(m) = O(logm)
    = O(loglogn) /* Since n = 2^m */
    Now, let us go back to the original recursive functio

  •   Question 7

    An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

    A : At least 2n - c comparisons, for some constant c, are needed.
    B : At most 1.5n - 2 comparisons are needed
    C : At least nLog2n comparisons are needed
    D : None of the above


  •  
    .

     Correct answer is :B


  •   Question 8

    Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?

    A : 0, 10, 110, 1110, 11110, 11111
    B : 11, 10, 011, 010, 001, 000
    C : 11, 10, 01, 001, 0001, 0000
    D : 110, 100, 010, 000, 001, 111


  •  
    .

     Correct answer is :A

     Solution :
      We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.
    The letters a, b, c, d, e, f have probabilities 
    1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 
    
                     1
                   /   
                  /     
                 1/2    a(1/2)
                /  
               /    
              1/4  b(1/4) 
             /   
            /     
           1/8   c(1/8) 
          /  
         /    
     

  •   Question 9

    Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?

    A : 3
    B : 2.1875
    C : 2.25
    D : 1.19375


  •  
    .

     Correct answer is :D

     Solution :
      We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.
    The letters a, b, c, d, e, f have probabilities 
    1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 
    
                     1
                   /   
                  /     
                 1/2    a(1/2)
                /  
               /    
              1/4  b(1/4) 
             /   
            /     
           1/8   c(1/8) 
          /  
         /   

  •   Question 10

    The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is



    A : MNOPQR
    B : NQMPOR
    C : QMNPRO
    D : QMNPOR


  •  
    .

     Correct answer is :C


  •   Question 11

    The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

    A : θ (n)
    B : θ (m)
    C : θ (m+n)
    D : θ (mn)


  •  
    .

     Correct answer is :C

     Solution :
      Number of connected components in undirected graph can simply calculated by doing a BFS or DFS. The best possible time complexity of BFS and DFS is O(m + n).

  •   Question 12

    Which of the following statements is true for every planar graph on n vertices?

    A : The graph is connected
    B : The graph is Eulerian
    C : The graph has a vertex-cover of size at most 3n/4
    D : The graph has a independent set of size at least n/3


  •  
    .

     Correct answer is :C

     Solution :
      A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A) FALSE: A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B) FALSE: An Eulerian Graph may or may not be planar. An undirected graph is eulerian if all vertices have even degree.

  •   Question 13

    Consider the following functions:
    f(n) = 2n
    g(n) = n!
    h(n) = nlogn
    Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?


    A : f(n) = O(g(n)); g(n) = O(h(n))
    B : f(n) = Ω (g(n)); g(n) = O(h(n))
    C : g(n) = O(f(n)); h(n) = O(f(n))
    D : h(n) = O(f(n)); g(n) = Ω(f(n))


  •  
    .

     Correct answer is :D

     Solution :
      According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) ) We can easily see above order by taking logs of the given 3 functions

  •   Question 14

    The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

    A : θ (n)
    B : θ (log n)
    C : θ (log*n)
    D : 1


  •  
    .

     Correct answer is :B


  •   Question 15

    Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

    A : T(n) <= 2T(n/5) + n
    B : T(n) <= T(n/5) + T(4n/5) + n
    C : T(n) <= 2T(4n/5) + n
    D : T(n) <= 2T(n/2) + n


  •  
    .

     Correct answer is :B

     Solution :
      For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

  •   Question 16

    The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?

    A : X[i, j] = X[i - 1, j] V X[i, j -ai]
    B : X[i, j] = X[i - 1, j] V X[i - 1, j - ai]
    C : X[i, j] = X[i - 1, j] /\ X[i, j - ai]
    D : X[i, j] = X[i - 1, j] /\ X[i -1, j - ai]


  •  
    .

     Correct answer is :B

     Solution :
      X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

  •   Question 17

    Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to



    A : only vertex a
    B : only vertices a, e, f, g, h
    C : only vertices a, b, c, d
    D : all the vertices


  •  
    .

     Correct answer is :D

     Solution :
      Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.

  •   Question 18

    We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

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


  •  
    .

     Correct answer is :B


  •   Question 19

    Let xn denote the number of binary strings of length n that contain noconsecutive 0s. Which of the following recurrences does Xn satisfy?

    A : xn = 2xn-1
    B : xn=xfloor(n/2) +1
    C : xn=xfloor(n/2) +n
    D : xn=xn-1+xn-2


  •  
    .

     Correct answer is :D


  •   Question 20

    Let xn denote the number of binary strings of length n that contain noconsecutive 0s.The value of X5 is

    A : 5
    B : 7
    C : 8
    D : 16


  •  
    .

     Correct answer is :C

     Solution :
     
    Since, X(n) = X(n - 1) + X(n - 2)
    X5 = X4 + X3
    X4 = X3 + X2 = 5 + 3 = 8
    Therefore, X5 = 8 + 5 = 13

  •   Question 21

    The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?

    A : X[i, j] = X[i - 1, j] V X[i, j -ai]
    B : X[i, j] = X[i - 1, j] V X[i - 1, j - ai]
    C : X[i, j] = X[i - 1, j] V X[i, j - ai]
    D : X[i, j] = X[i - 1, j] V X[i -1, j - ai]


  •  
    .

     Correct answer is :B

     Solution :
      X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.

  •   Question 22

    The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,...,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W? Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

    A : X[1, W]
    B : X[n, 0]
    C : X[n, W]
    D : X[n-1, n]


  •  
    .

     Correct answer is :C

     Solution :
      If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.

  • MY REPORT
    TOTAL = 22
    ANSWERED =
    CORRECT / TOTAL = /22
    POSITIVE SCORE =
    NEGATIVE SCORE =
    FINAL SCORE =