Follow Us :

Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > Performance Analysis of Algorithms and Recurrences

96. 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 ali leaders in an array

  • Option : B
  • Explanation :
    The best algorithm is we can solve in linear time using right to left pass.
Cancel reply
Cancel reply

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

  • Option : C
  • Explanation :
    a1, a2 .....................an
    b1, b2 .....................bn
    In order to find out the largest span, check the sums of
    ai +............aj and bi +..............bj at each step.
    If a1 + a2 = b1 + b2 go on, check a1 + a2 + a3 and b1 + b2 + b3.
    If not, then check a2 + a3 and b2 + b3
    Similarly a check is done at each of the n places during traversal. A separate variable has to be kept that contains the maximum span observed hitherto
    Hence fastest algorithm computes with (~) (n) time and space.
Cancel reply
Cancel reply

98. Following algorithm (s) can be used to sort n integers in the range [1... n3] in O(n) time?

  • Option : D
  • Explanation :
    Radix sort is counting based sorting technical the time complexity is Q(n).
Cancel reply
Cancel reply

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

  • Option : A
  • Explanation :
    From the list of given n numbers [say n is even], Pick up first two elements, compare them
    assign Current – min = min of two numbers
    Current – max = max of two numbers
    From the remaining n – 2 numbers, take pairs wise and follow this process given below.

    1. Compare two elements
    Assign min = min of two numbers
    max = max of two numbers

    2. Compare min and current – min
    Assign current – min
    = min{current– min,min}

    3. Compare max and current – max
    Assign current – max
    = max{current – max, max}

    Repeat above procedure for all the remaining pairs of numbers. We can observe that each of pair requires 3 comparisons
    1. for finding min and max
    2. For updating current – min
    3. for updating current – max
    But for initial pair we need only one comparison not 3.
    ∴ Total number of comparisons

    Here n =100, so number of comparisons = 148.
Cancel reply
Cancel reply

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

  • Option : B
  • Explanation :
    Given: n numbers
    To find: Tightest upper bound on number of swaps required to sort n numbers using selection sort.
    Analysis: In selection sort, in the unsorted part of the array, we find the minimum element and swap it with the value placed at the index where the unsorted array starts.
    Hence, for each element to put it in its sorted position, we will do some swaps. In each itenation, when we find the minimum and place it in its sorted position, we do only one swap.
    There are n such iterations, since maximum number of positions to sort is n.
    Hence, there are n.O(1) swaps
    ⇒ O(n) swaps.
    ∴ The solution is (B)
Cancel reply
Cancel reply
Related Quiz.
Performance Analysis of Algorithms and Recurrences