GATE Questions & Answers of Divide-and-conquer

What is Divide-and-conquer ?

In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until th

What is the Weightage of Divide-and-conquer in GATE Exam?

Total 17 Questions have been asked from Divide-and-conquer topic of Algorithms subject in previous GATE papers. Average marks 1.53.

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$?

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 __________. 

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

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

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?

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

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

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


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_____.


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

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

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

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

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?

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

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

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?