Table of contents
1.
Introduction
2.
Key Takeaways
Last Updated: Mar 27, 2024

Divide and Conquer

Author Apoorv
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

It's an algorithmic pattern called Divide and Conquer. The design of algorithmic approaches is to take a disagreement over a large input, break it down into little pieces, solve the problem on each of the small bits, and then integrate the piecewise solutions into a global solution.

Question 1: Which of these algorithms is NOT a divide & conquer algorithm by nature?

  1. Cooley-Tukey fast Fourier transform
  2. Euclidean algorithm to compute the greatest common divisor
  3. Heap Sort
  4. Merge Sort

Answer: C

You can see the divide and conquer algorithm from here. All of these algorithms follow the divide and conquer except for heap sort. To read more about heap sort you can refer to here.

 

Question 2: Suppose P is a program of QuickSort that sorts the numbers in ascending order. While sorting, it uses the first element as a pivot. Let x1 and x2 be the total number of comparisons made by this quicksort program for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Then choose the correct one from the above options.

  1. x1 > x2
  2. x1 < x2
  3. x1 == x2
  4. Can’t be determined

Answer: A

Always remember the fact that Whenever the first element or the last element is chosen as the pivot in quick sort then it would be a worst-case scenario for the sorted arrays.

The recurrence relation will look like this for the above case

T(n) = T(n-1) + O(n)

 

Question 3: Given below is a program in C what does this program compute?

int main() 

   int a, b, m, n; 

   scanf ("%d %d", &a, &b); 

   /* a > 0 and b > 0 */

   m = a; n = b; 

   while (m != n) 

   { 

      if(m>n) 

         m = m - n; 

      else

         n = n - m; 

   } 

   printf("%d", n); 

}

  1. a + b using repeated subtraction
  2. a mod b using repeated subtraction
  3. the greatest common divisor of a and b
  4. the least common multiple of a and b

Answer: C

This program is an implementation of the Euclid algorithm to find the GCD  which uses the concept of Divide and Conquer you can see the detailed implementation form here.

 

Question 4:Which one of the below options correctly determines the solution of this recurrence relation with T(1) = 1?

T(n) = 2T(n/2) + Logn 

  1.  Θ(nLogn)
  2.  Θ(n*n)
  3.  Θ(Logn)
  4. Θ(n)

Answer: D

T(n) = 2T(n/2) + log n

 T(1) = 1

Substitute n = 2^k

T(2^k)  = k + 2T(2^(k-1))

T(2^k)  = k + 2(k-1) + 4T(2^(k-2))

        = k + 2(k-1) + 4(K-2) + 8T(2^(k-3))

        = k + 2(k-1) + 4(K-2) + 8(k-3) + 16T(2^(k-4))

        = k + 2(k-1) + 4(K-2) + 8(k-3) + ...... + 2^kT(2^(k-k))

        = k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^kT(1)

        = k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^k  --------(1)

2T(2^k) =     2k     + 4(k-1) + 8(K-2) + ...... + 2*2^k + 2^(k+1) --------(2)

Subtracting 1 from 2, we get below

T(2^k) = - k + 2 + 4 ......    2^(k-2) + 2^(k-1) + 2^k + 2^(k+1)

           = - k + 2 * (1 + 2 + 4 + ..... 2^k)

           = -k + [2*(2^k - 1)] / [2-1]

           = -k + [2*(2^k - 1)]

T(n) = -Logn + 2*(n - 1)

T(n)  = Θ(n) 

 

Question 5: Given below are the two statements. Choose the correct options regarding the Bellman-Ford shortest path algorithm?

A: Always finds a negative weighted cycle, if one exists.

B: Finds whether any negative weighted cycle is reachable from the source.

  1. A Only
  2. B Only
  3. Both A and B
  4. Neither A nor B

Answer: B

A single source shortest path algorithm is the Bellman-Ford algorithm. As a result, it can only discover cycles that can be reached from a certain source, not negative weight cycles. Consider a disconnected situation in which a negative weight cycle can't be reached at all from the source. This is a very important application of Divide and Conquer.

If there is a negative weight cycle, it will appear in the shortest path since a negative weight cycle will always generate a shorter path when iterated through the cycle.

 

Question 6:Consider an imaginary situation where you can not use this function to calculate the power of a given number 'power (pow() function in C)' and you still need to calculate a^n, where ‘a’ can be any number and ‘n’ is a positive integer. What can be the best possible time complexity of your power function?

  1. O(nLogn)
  2. O(n)
  3. O(LogLogn)
  4. O(Logn)

Answer: D

We can use the concept of divide and conquer to find power. Divide and conquer will do the work for us in logarithmic time. Below is the implementation for the same

// Function to calculate a^n in O(logn) using divide and conquer
int power(int a, unsigned int n)
{
    int temp;
    if( n == 0)
        return 1;
    temp = power(a, n / 2);
    if (n % 2 == 0)
        return temp * temp;
    else
        return a* temp * temp;
}
You can also try this code with Online C++ Compiler
Run Code

 

Question 7:You are given an array having n elements. Consider a case where you always implement a quicksort algorithm by always choosing the central element of the array as the pivot element. Then the tightest upper bound for the worst-case performance is

  1. O(n2)
  2. O(nLogn)
  3. O(n3)
  4. Theta(nLogn)

Answer: A

For any input, there are some possibilities for which the worst case will be O(n2). In some cases, choosing the middle element minimizes the chances of encountering O(n2), but in the worst case, it might go to O(n2). Whichever element we take as Pivot, either first or middle, the worst case will always be O(n2) since Pivot is fixed in position. While choosing a random pivot element minimizes the chances of encountering always worst-case i.e. O(n2).

 

Question 8: Find the minimum number of arithmetic operations required to evaluate the given polynomial P(X) = X5 + 4X3 + 6X + 5 for any given value of X using only one temporary variable.

  1. 4
  2. 8
  3. 7
  4. 6

Answer: C

P(X) = x5 + 4x3 + 6x + 5

     =x ( x4 + 4x2 + 6 ) +5

     =x ( x ( x3 + 4x ) + 6 ) + 5

     =x ( x ( x ( x2 + 4 ) ) + 6 ) + 5

     =x ( x ( x (x (x) + 4 ) ) + 6 ) + 5

Let T be a temporary variable to store intermediate results.

1. T = (x) * (x)

2. T = T + 4

3. T = (x) * (T)

4. T = (x) * (T)

5. T = T + 6

6. T = (x) * T

7. T = T + 5

Thus, we need 7 operations if we are to use only one temporary variable.

 

Question 9:The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is  

  1. 145
  2. 147
  3. 148
  4. 142

Answer: C

You need to follow these steps in order to find the minimum and maximum element out of n numbers:

1. Pick 2 elements(x, t) then compare them. (say x > y)

2. Update min by comparing (min, y)

3. Update max by comparing (max, x)

Hence, we need 3 comparisons for every 2 elements, so we can conclude that the total number of required comparisons will be (3n)/2 – 2 because we do not need to update min or max in the very first step.

The Recurrence relation obtained will be this : 

T(n) = T(⌈n/2⌉)+T(⌊n/2⌋)+2 = 2T(n/2)+2 = ⌈3n/2⌉-2

Now simply put the value of n here n=100, (3*100/2)-2 = 148 which is answer.

 

Question 10:The recurrence relation that arises in relation with the complexity of binary search is:

  1. T(n) = 2T(n/ 2) + k , where k is constant
  2. T(n) = T(n / 2) + k , where k is constant
  3. T(n) = T(n / 2) + log n
  4. T(n) = T(n / 2) + n

Answer: C

Binary Search is considered to be a linear searching algorithm and it takes O(log n) time when the array is sorted. Binary search is also the most commonly used application of Divide and Conquer.

Key Takeaways

In this article, we have extensively discussed the important questions from the Divide and Conquer and some previously asked questions in the gate exam.

Until then, All the best for your future endeavors, and Keep Coding. "We hope that this blog has helped you enhance your knowledge regarding this problem, and if you would like to learn more, check out our articles on  Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!”

Live masterclass