Loading

SET 6


  Question 1

A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

A : An array of 50 numbers
B : An array of 100 numbers
C : An array of 500 numbers
D : A dynamically allocated array of 550 numbers


  •  
    .

     Correct answer is :A

     Solution :
      An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value

  •   Question 2

    An undirected graph C has n nodes. Its adjacency matrix is given by an n n square matrix whose
    (i) diagonal elements are 0's, and
    (ii) non-diagonal elements are l's.
    Which one of the following is TRUE?


    A : Graph G has no minimum spanning tree (MST)
    B : Graph G has a unique MST of cost n-1
    C : Graph G has multiple distinct MSTs, each of cost n-1
    D : Graph G has multiple spanning trees of different costs


  •  
    .

     Correct answer is :C

     Solution :
      If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1.

  •   Question 3

    The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be

    A : O(n)
    B : O(n logn)
    C : O(n3/2)
    D : O(n3)


  •  
    .

     Correct answer is :D

     Solution :
      In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.
    In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node othe

  •   Question 4

    Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?

    A : T(n) = O(n2)
    B : T(n) = θ(n log n)
    C : T(n) = Ω(n2)
    D : T(n) = O(n log n)


  •  
    .

     Correct answer is :C

     Solution :
      The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).
    T(n) = θ(nLogn)
    By definition of Big O notation, we can say.
    θ(nLogn) = O(nLogn) = O(n^2)
    θ(nLogn) ca be equal to Ω (n) or Ω (nLogn), but not Ω (n^2)

  •   Question 5

    Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

    A : O(| V |2)
    B : O (| E | + | V | log | V |)
    C : O (| V | log | V |)
    D : O ((| E | + | V |) log | V |)


  •  
    .

     Correct answer is :D


  •   Question 6

    Suppose there are ⌈ log n ⌉ sorted lists of ⌊ n/log n ⌋ elements each. The time complexity of producing a sorted list of all these elements is : (Hint : Use a heap data structure)

    A : O(n log log n)
    B : θ (n log n)
    C : Ω (n log n)
    D : Ω (n3/2)


  •  
    .

     Correct answer is :A

     Solution :
      We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.
    x = n/Logn y = Logn We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

  •   Question 7

    Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y The edge e must definitely belong to:

    A : the minimum weighted spanning tree of G
    B : the weighted shortest path from s to t
    C : each path from s to t
    D : the weighted longest path from s to t


  •  
    .

     Correct answer is :A

     Solution :
      This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge.

  •   Question 8

    Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum weight amongst all those edges that have one vertex in X and one vertex in Y.

    A : a path from s to t in the minimum weighted spanning tree
    B : a weighted shortest path from s to t
    C : an Euler walk from s to t
    D : a Hamiltonian path from s to t


  •  
    .

     Correct answer is :B


  •   Question 9

    We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.
    What is the maximum profit earned?




    A : 147
    B : 165
    C : 167
    D : 175


  •  
    .

     Correct answer is :A

     Solution :
     
    Task     T1  T2	 T3  T4  T5  T6	 T7 T8  T9
    Profit   15  20	 30  18  18  10	 23 16  25
    Deadline 7   2 	 5   3 	 4   5 	 2  7   3 
    

    To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1. We get the maximum profit as 23 + 20 + 25 + 18 + 30 + 16 + 15 = 147

  •   Question 10

    We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.Are all tasks completed in the schedule that gives maximum profit?

    A : All tasks are completed
    B : T1 and T6 are left out
    C : T1 and T8 are left out
    D : T4 and T6 are left out


  •  
    .

     Correct answer is :D

     Solution :
     
    Task     T1  T2	 T3  T4  T5  T6	 T7 T8  T9
    Profit   15  20	 30  18  18  10	 23 16  25
    Deadline 7   2 	 5   3 	 4   5 	 2  7   3 
    

    To maximize profit, we can finish tasks in following order T7, T2, T9, T5, T3, T8, T1

  •   Question 11

    Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is:

    A : n-1
    B : 2n-2
    C : nC2
    D : 2


  •  
    .

     Correct answer is :B

     Solution :
      Minimum spanning tree of such a graph is
    v1
      
        v2
          
           v3
             
              v4
                .
                  .
                    .
                     vn

    Weight of the minimum spanning tree
    = 2|2 1| + 2|3 2| + 2|4 3| + 2|5 4| . + 2| n (n-1) |
    = 2n 2

  •   Question 12

    To implement Dijkstras shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

    A : Queue
    B : Stack
    C : Heap
    D : B-Tree


  •  
    .

     Correct answer is :A

     Solution :
      The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.

  •   Question 13

    Which one of the following in place sorting algorithms needs the minimum number of swaps?

    A : Quick sort
    B : Insertion sort
    C : Selection sort
    D : Heap sort


  •  
    .

     Correct answer is :C

     Solution :
      For selection sort, number of swaps required is minimum ( O(n) ).

  •   Question 14

    An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array.

    A : Solves it in linear time using a left to right pass of the array
    B : Solves it in linear time using a right to left pass of the array
    C : Solves it using divide and conquer in time θ(nlogn)
    D : Solves it in time Theta(n^2)


  •  
    .

     Correct answer is :B

     Solution :
      Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes its value, print it.
    So it will take linear time.

  •   Question 15

    Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskals algorithm?



    A : (ab),(df),(bf),(dc),(de)
    B : (ab),(df),(dc),(bf),(de)
    C : (df),(ab),(dc),(bf),(de)
    D : (df),(ab),(bf),(de),(dc)


  •  
    .

     Correct answer is :D

     Solution :
      The edge (d-e) cannot be considered before (d-c) in Kruskal's minimum spanning tree algorithm because Kruskals algorithm picks the edge with minimum weight from the current set of edges at each step.

  •   Question 16

    Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and n in G are at least 2. which one of the following statements is true?

    A : There must exist a vertex w adjacent to both u and n in G
    B : There must exist a vertex w whose removal disconnects u and n in G
    C : There must exist a cycle in G containing u and n
    D : There must exist a cycle in G containing u and all its neighbours in G.


  •  
    .

     Correct answer is :B

     Solution :
      Since they are leaves in DFS, they must be separable by a vertex.

  •   Question 17

    An implementation of a queue Q, using two stacks S1 and S2, is given below:
    void insert(Q, x)
    {
    push (S1, x);
    }
    void delete(Q){
    if(stack-empty(S2)) then
    if(stack-empty(S1)) then {
    print(Q is empty);
    return;
    }
    else while (!(stack-empty(S1))){
    x=pop(S1);
    push(S2,x);
    }
    x=pop(S2);
    }
    Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?


    A : n+m <= x < 2n and 2m <= y <= n+m
    B : n+m <= x < 2n and 2m<= y <= 2n
    C : 2m <= x < 2n and 2m <= y <= n+m
    D : 2m <= x <2n and 2m <= y <= 2n


  •  
    .

     Correct answer is :A

     Solution :
      The order in which insert and delete operations are performed matters here. The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
    The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed

  •   Question 18

    A set X can be represented by an array x[n] as below in the image:
    Consider the following algorithm in which x,y and z are Boolean arrays of size n:
    algorithm zzz(x[] , y[], z [])
    {
       int i;
       for (i=O; i<n; ++i)
         z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])
    }

    The set Z computed by the algorithm is:




    A : (X ∪ Y)
    B : (X ∩ Y)
    C : (X-Y) ∩ (Y-X)
    D : (X-Y) ∪ (Y-X)


  •  
    .

     Correct answer is :A

     Solution :
      The expression x[i] ^ ¬ y[i]) results the only 1s in x where corresponding entry in y is 1. The expression ¬ x[i] ^ y[i]) results the only 1s in y where corresponding entry in x is 1.

  •   Question 19

    Consider the following recurrence: Which one of the following is true?
    T(n) = 2T( ⌈√n ⌉) + 1, T(1) = 1


    A : T(n) = θ(loglogn)
    B : T(n) = θ(logn)
    C : T(n) = θ(√n)
    D : T(n) = θ(n)


  •  
    .

     Correct answer is :B

     Solution :
      This question can be solved by first change of variable and then Master Method.
    Let n = 2^m
    T(2^m) = T(2^(m/2)) + 1
    Let T(2^m) = S(m)
    S(m) = 2S(m/2) + 1
    Above expression is a binary tree traversal recursion whose time complexity is (m). You can also prove using Master theorem.
    S(m) = (m)
    = (logn) /* Since n = 2^m */
    Now, let us go back to the original recursive function T(n)
    T(n) = T(2^m) = S(m)
    =

  •   Question 20

    Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

    A : O(n2 Logn)
    B : O(n2 )
    C : O(n Logn Logn)
    D : O(n Logn)


  •  
    .

     Correct answer is :D

     Solution :
      If we use median as a pivot element, then the recurrence for all cases becomes
    T(n) = 2T(n/2) + O(n)
    The above recurrence can be solved using Master Method. It falls in case 2 of master method.

  •   Question 21

    Given two arrays of numbers a1, a2, a3,...an and b1, b2, .. bn where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that ai + ai+1, ....aj = bi, bi+1, .. bj. or report that there is not such span,

    A : Takes O(n3) and Ω (2n) time if hashing is permitted
    B : Takes O(n3) and Ω (n2.5) time in the key comparison model
    C : Takes θ(n) time and space
    D : Takes O(√ n) time only if the sum of the 2n elements is an even number


  •  
    .

     Correct answer is :C


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