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

##### Show Answer

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

##### Show Answer

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.

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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

$T\left(n\right)=2T\left(\frac{n}{2}\right)+\mathrm{log}n$

##### Show Answer

The minimum number of arithematic operation required to evaluate the polynomial $P\left(X\right)={X}^{5}+4{X}^{3}+6X+5$ for a given value of X,using only one temporary variable is_____.

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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?