The GATE Grind

GATE Algorithms: Divide-and-Conquer – Previous Year Questions

8 GATE previous year questions on Divide-and-Conquer (Algorithms, Computer Science) with answers and explanations, from every paper.

8 questions worth 12 marks in all (4 1-mark, 4 2-mark). Asked between 2008 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2008 CS Q43 (2 marks, Multiple choice) – Quicksort has a pivot routine splitting every list so each side contains at least one-fifth of the elements. If T(n) counts sorting comparisons, then
  2. GATE 2009 CS Q39 (2 marks, Multiple choice) – Quicksort chooses the (n/4)th smallest element as pivot for n elements using an O(n)-time selection algorithm. What is its worst-case time complexity?
  3. GATE 2015 CS (CS3) Q63 (2 marks, Numerical answer) – Find DOSOMETHING(c,a,n) for k=4,c=(1,0,1,1),a=2,n=8.
  4. GATE 2015 CS (CS2) Q49 (2 marks, Multiple choice) – partition(a,n) uses a[0] as pivot, moves values ≤pivot left and greater values right, and places the pivot last in the left part. Complete the…
  5. GATE 2014 CS (CS2) Q23 (1 mark, Multiple choice) – Which gives the solution of T(n)=2T(n/2)+ n, T(1) = 1?
  6. GATE 2019 CS Q35 (1 mark, Numerical answer) – Consider a sequence of 14 elements: A=[-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0]. The subsequence sum S(i,j)= k=ijA[k]. Determine the maximum of S(i,j),…
  7. GATE 2026 CS (CS2) Q32 (1 mark, Numerical answer) – Consider an array A=[10,7,8,19,41,35,25,31]. Suppose merge sort is executed on A to sort it in increasing order. The algorithm will carry out a total…
  8. GATE 2021 CS (CS1) Q12 (1 mark, Multiple choice) – 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…