Previously Asked GATE Questions on Divide and Conquer

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

(A) Euclidean algorithm to compute the greatest common divisor
(B) Heap Sort
(C) Cooley-Tukey fast Fourier transform
(D) Quick Sort

Answer: (B)
Explanation: See Divide and Conquer

Question 2: Consider the following C program

What does the program compute?

(A) x + y using repeated subtraction
(B) x mod y using repeated subtraction
(C) the greatest common divisor of x and y
(D) the least common multiple of x and y

Answer: (C)
Explanation: This is an implementation of Euclid’s algorithm to find GCD

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:

(A) 3
(B) 4
(C) 6
(D) 9

Answer: (A)
Explanation: Multiplications can be minimized using following order for evaluation of the given expression. p(x) = a0 + x(a1 + x(a2 + a3x))

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?

(A) O(n)
(B) O(nLogn)
(C) O(Logn)
(D) O(n^2)

Answer: O(B)
Explanation: See http://www.w3wiki.org/divide-and-conquer-maximum-sum-subarray/

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?

(A) O(n)
(B) O(nLogn)
(C) O(LogLogn)
(D) O(Logn)

Answer: (D)
Explanation: We can calculate power using divide and conquer in O(Logn) time.

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

(A) 1 Only
(B) 1 & 2 only
(C) 1, 2 and 3 only
(D) 1, 2, 3 and 4

Answer: (C)
Explanation: See http://www.w3wiki.org/search-an-element-in-a-sorted-and-pivoted-array/

Question 7: Consider the problem of computing min-max in an unsorted array where min and max are minimum and maximum elements of array. Algorithm A1 can compute min-max in a1 comparisons without divide and conquer. Algorithm A2 can compute min-max in a2 comparisons by scanning the array linearly. What could be the relation between a1 and a2 considering the worst case scenarios?

(A) a1 < a2
(B) a1 > a2
(C) a1 = a2
(D) Depends on the input

Answer: (B)
Explanation: When Divide and Conquer is used to find the minimum-maximum element in an array, Recurrence relation for the number of comparisons is
T(n) = 2T(n/2) + 2 where 2 is for comparing the minimums as well the maximums of the left and right subarrays
On solving, T(n) = 1.5n – 2.
While doing linear scan, it would take 2*(n-1) comparisons in the worst case to find both minimum as well maximum in one pass.

Question 8: Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?

(A) t>2n−2
(B) t>3⌈n/2⌉ and t≤2n−2
(C) t>n and t≤3⌈n/2⌉
(D) t>⌈log2(n)⌉ and t≤n

Answer: (B)
Explanation: It will take t≤2n−2 comparisons without divide and conquer technique. It will take t≤ 3⌈n/2⌉ – 2 with divide and conquer technique.

Question 9: A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

(A) Θ(nlogn)
(B) Θ(n)
(C) Θ(logn)
(D) Θ(1)

Answer: (D)
Explanation: Pick any two elements from the root, and return minimum of these two. So, time is Θ(1).

Question 10: Consider the following array. 

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

(A) Selection sort
(B) Mergesort
(C) Insertion sort
(D) Quicksort using the last element as pivot

Answer: (C)
Explanation: Since, given array is almost sorted in ascending order, so Insertion sort will give its best case with time complexity of order O(n).

Those preparing for the GATE (Graduate Aptitude Test in Engineering) exam in 2024 face many algorithmic challenges. Among the various algorithmic paradigms, “Divide and Conquer” stands out as a powerful approach to problem-solving. In this comprehensive guide for the GATE Exam, Divide and Conquer, and its applications will be explored through a range of important topics. These notes aim to provide a solid foundation for mastering these concepts in preparation for the upcoming GATE exam.