Questions & Answers of Divide-and-conquer

Question No. 12

Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for $a_n$?

Question No. 37

Consider the recurrence relation $\style{font-family:'Times New Roman'}{a_1=8,a_n=6n^2+2n+a_{n-1}.\mathrm{Let}\;a_{99}=K\times10^4.}$ The value of K is __________. 

Question No. 14

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n (2) numbers? In the recurrence equations given in the options below, c is a constant.

Question No. 45

Let an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?

Question No. 24

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

Question No. 49

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

Question No. 52

Consider the following pseudo code. What is the total number of multiplications to be performed?

  D = 2
    for i = 1 to n do
      for j = i to n do
        for k = j + 1 to n do
          D = D * 3

Question No. 123

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

Tn=2Tn2+logn

Question No. 221

The minimum number of arithematic operation required to evaluate the polynomial PX=X5+4X3+6X+5 for a given value of X,using only one temporary variable is_____.

 

Question No. 224

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

Question No. 5

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

Question No. 39

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

Question No. 38

Four matrices M1, M2 , M3 and M4, of 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

Question No. 39

In quick sort , for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

Question No. 43

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

Question No. 14

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

Question No. 44

In the following C function, let nm.

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?