# Exercise: Questions on Divide and Conquer

Questions on Divide and Conquer : Question 1 :
Which of the following algorithms is NOT a divide & conquer algorithm by nature?

 Euclidean algorithm to compute the greatest common divisor Heap Sort  Correct Cooley-Tukey fast Fourier transform Quick Sort
Questions on Divide and Conquer : Question 2 :
Consider the following C program
```int main()
{
int x, y, m, n;
scanf ("%d %d", &x, &y);
/* x > 0 and y > 0 */
m = x; n = y;
while (m != n)
{
if(m>n)
m = m - n;
else
n = n - m;
}
printf("%d", n);
}
```
What does the program compute? (GATE CS 2004)

 x + y using repeated subtraction x mod y using repeated subtraction the greatest common divisor of x and y  Correct the least common multiple of x and y
Questions on Divide and Conquer : Question 3 :
Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:

 3  Correct 4 6 9
Questions on Divide and Conquer : Question 4 :
Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10}, the maximum subarray sum is 45. The naive solution for this problem is to calculate sum of all subarrays starting with every element and return the maximum of all. We can solve this using Divide and Conquer, what will be the worst case time complexity using Divide and Conquer.

 O(n) O(nLogn)  Correct O(Logn) O(n^2)
Questions on Divide and Conquer : Question 5 :
Consider a situation where you don't have function to calculate power (pow() function in C) and you need to calculate x^n where x can be any number and n is a positive integer. What can be the best possible time complexity of your power function?

 O(n) O(nLogn) O(LogLogn) O(Logn)  Correct
Questions on Divide and Conquer : Question 6 :
Consider the problem of searching an element x in an array 'arr[]' of size n. The problem can be solved in O(Logn) time if. 1) Array is sorted 2) Array is sorted and rotated by k. k is given to you and k <= n 3) Array is sorted and rotated by k. k is NOT given to you and k <= n 4) Array is not sorted

 1 Only 1 & 2 only 1, 2 and 3 only  Correct 1, 2, 3 and 4
Questions on Divide and Conquer : Question 7 :
The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates xa and xb for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is the solution. The procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to be put in place of? So that it follows all steps of the secant method? Secant
```Initialize: xa, xb, ε, N     // ε = convergence indicator
fb = f(xb) i = 0
while (i < N and |fb| > ε) do
i = i + 1                 // update counter
xt = ?                    // missing expression for
// intermediate value
xa = xb                   // reset xa
xb = xt                   // reset xb
fb = f(xb)                // function value at new xb
end while
if |fb| > ε
then // loop is terminated with i = N
write “Non-convergence”
else
write “return xb”
end if```

 xb – (fb– f(xa)) fb/ (xb – xa) xa– (fa– f(xa)) fa/ (xb – xa) xb – (fb – xa) fb/ (xb – fb(xa) xa – (xb – xa) fa/ (fb – f(xa))  Correct
Questions on Divide and Conquer : Question 8 :
Suppose you are provided with the following function declaration in the C programming language.
`   int partition (int a[], int n); `
The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k â¤ n
```int kth_smallest (int a[], int n, int k)
{
int left_end = partition (a, n);
if (left_end+1==k)
{
return a [left_end];
}
if (left_end+1 > k)
{
return kth_smallest (____________________);
}
else
{
return kth_smallest (____________________);
}
}
```
The missing argument lists are respectively

 (a, left_end, k) and (a+left_end+1, n–left_end–1, k–left_end–1)  Correct (a, left_end, k) and (a, n–left_end–1, k–left_end–1) (a, left_end+1, N–left_end–1, K–left_end–1) and(a, left_end, k) (a, n–left_end–1, k–left_end–1) and (a, left_end, k)