Loading

SET 3


  Question 1

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n - 1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Initialize Ln-1 =1 For all i such that 0 <= i <= n-2
Finally the length of the longest monotonically increasing sequence is Max( L0 ,L1 ,...,L n-1) . Which of the following statements is TRUE?




A : The algorithm uses dynamic programming paradigm
B : The algorithm has a linear complexity and uses branch and bound paradigm
C : The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
D : The algorithm uses divide and conquer paradigm.


  •  
    .

     Correct answer is :A


  •   Question 2

    Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
    f1(n) = 2n ; f2(n) =n3/2; f3(n) = n log2n; f4(n) = nlog n


    A : f3 , f2, f4, f1
    B : f3,f2,f1,f4
    C : f2,f3,f1,f4
    D : f2,f3,f4,f1


  •  
    .

     Correct answer is :A


  •   Question 3

    Four matrices M1, M2, M3 and M4 are dimensions p q, q r, r s and s t respectively can be multiplied in several ways with different number of total scalar multiplications. For example When multiplied as (( M1 * M2) ( M3* M4 )) the total number of scalar multiplications is pqr+rst+prt. When multiplied as (((M1 * M2 )*M3 )*M4 ) , the total number of scalar multiplications is pqr+prs+pst. If p=10, q=100, r=20, s=5 and t=80, then the minimum number of scalar multiplications needed is

    A : 24800
    B : 44000
    C : 19000
    D : 25000


  •  
    .

     Correct answer is :C

     Solution :
      We can get (M1 * (M2 * M3) ) * M4) = The total number of scalar multiplication is = qrs + pqs + pst =10000 + 5000 + 4000 = 19000

  •   Question 4

    Consider the following recursive C function that takes two arguments
    unsigned int foo ( unsigned int n, unsigned int r ) {
    if (n > 0 ) return (n%r) + foo ( n / r, r )) ;
    else return 0;
    }
    What is the return value of the function foo when it is called as foo (513, 2)?


    A : 9
    B : 8
    C : 5
    D : 2


  •  
    .

     Correct answer is :D


  •   Question 5

    Consider the following recursive C function that takes two arguments
    unsigned int foo ( unsigned int n, unsigned int r ) {
    if (n > 0 ) return (n%r) + foo ( n / r, r )) ;
    else return 0;
    }
    What is the return value of the function foo when it is called as foo (345, 10)?


    A : 345
    B : 12
    C : 5
    D : 3


  •  
    .

     Correct answer is :B


  •   Question 6

    An undirected graph G(V,E) contains n ( n >2 ) nodes named v1 , v2 ,....vn . Two nodes vi , vj are connected if and only if 0 < |i - j| <= 2. Each edge ( vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.
    What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?




    A : 1/12 (11n2-5n)
    B : n2 -n +1
    C : 6n -11
    D : 2n +1


  •  
    .

     Correct answer is :B


  •   Question 7

    An undirected graph G(V,E) contains n ( n >2 ) nodes named v1 , v2 ,....vn . Two nodes vi , vj are connected if and only if 0 < |i - j| <= 2. Each edge ( vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.
    The length of the path from v5 to v6 in the MST of previous question with n = 10 is




    A : 11
    B : 25
    C : 31
    D : 41


  •  
    .

     Correct answer is :C

     Solution :
      12 + 8 + 4 + 3 + 6 + 10 = 31


  •   Question 8

    Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

    A : A(n) =Ω(W(n))
    B : A(n) = θ (W(n))
    C : A(n) = O(W(n))
    D : A(n) = o(W(n))


  •  
    .

     Correct answer is :C

     Solution :
      The average case time can be lesser than or even equal to the worst case. So A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same.

  •   Question 9

    The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

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


  •  
    .

     Correct answer is :D

     Solution :
      Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B The following sequence of steps are executed recursively 1.move n-1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)
    2.move disc n from A to C---------1
    3.move n-1 discs from B to C so they sit on disc n----- T(n-1)
    So, T(n) = 2T(n-1) +1

  •   Question 10

    The worst case running time to search for an element in a balanced binary search tree with n2n elements is

    A : θ (n log n)
    B : θ (n 2n)
    C : θ (n)
    D : θ (log n)


  •  
    .

     Correct answer is :C

     Solution :
      The worst case search time in a balanced BST on x nodes is logx. So, if x = n2n, then log(n2n) = logn + log(2n) = logn + n = θ(n)

  •   Question 11

    Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstras shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.



    A : SDT
    B : SBDT
    C : SACDT
    D : SACET


  •  
    .

     Correct answer is :D


  •   Question 12

    A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

    A : O( n log n)
    B : O( n2 log n)
    C : O( n2 + log n )
    D : O( n2 )


  •  
    .

     Correct answer is :B

     Solution :
      The height of the recursion tree using merge sort is logn and n2 comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n2 log n)

  •   Question 13

    Let G be a weighted graph with edge weights greater than one and G be the graph constructed by squaring the weights of edges in G. Let T and T be the minimum spanning trees of G and G respectively, with total weights t and t. Which of the following statements is TRUE?

    A : T = T with total weight t = t2
    B : T = T with total weight t < t2
    C : T ≠ T but total weight t = t2
    D : None of the above


  •  
    .

     Correct answer is :D

     Solution :
      Graph G is counter example for options (B) and (C) and Graph G1 is counter example for option (A)


  •   Question 14

    What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

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


  •  
    .

     Correct answer is :C

     Solution :
      Bellman-ford time complexity: θ( |V| |E| )
    For complete graph : |E| = n(n-1)/2
    |V| = n
    θ (n * n(n-1)/2) = θ (n3)

  •   Question 15

    A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero(the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

    A : This algorithm is equivalent to the first-come-first-serve algorithm
    B : This algorithm is equivalent to the Round Robin algorithm
    C : This algorithm is equivalent to the shortest-job-first algorithm
    D : This algorithm is equivalent to the shortest-remaining-time-first algorithm


  •  
    .

     Correct answer is :B

     Solution :
      The given scheduling definition takes two parameters, one is dynamically assigned process priority and the other is T time unit to re-evaluate the process priorities.
    This dynamically assigned priority will be deciding processes order in ready queue of round robin algorithm whose time quantum is same as T time units. As all the processes are arriving at the same time, they will be given same priority but soon after first T time burst remaining processes will get higher priorities

  •   Question 16

    Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

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


  •  
    .

     Correct answer is :B

     Solution :
      The maximum number of swaps that takes place in selection sort on n numbers is n

  •   Question 17

    Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter
    MultiDequeue (Q) {
    m =k
    while (Q is not empty) and (m >0) {
    Dequeue (Q)
    m = m - 1
    }
    }
    What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?


    A : θ (n)
    B : θ (n+k)
    C : θ (nk)
    D : θ (n2)


  •  
    .

     Correct answer is :A

     Solution :
      Initially the queue is empty and we have to perform n operations.
    i) One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be θ(n)
    or
    ii) We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2

  •   Question 18

    The number of elements that can be sorted in θ(logn) time using heap sort is

    A : θ (1)
    B : θ (√log n)
    C : θ (log n/ log logn)
    D : θ (log n)


  •  
    .

     Correct answer is :A

     Solution :
      After constructing a max-heap in the heap sort , the time to extract maximum element and then heapifying the heap takes θ(log n) time by which we could say that θ(log n) time is required to correctly place an element in sorted array. If θ(logn) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is θ(1)

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