Previous Year Questions: Divide and Conquer | Algorithms - Computer Science Engineering (CSE) PDF Download

Q1: 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) = A[k].
Determine the maximum of S(i, j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used). Answer:________  (2019)
(a) 25
(B) 12
(C) 29
(d) 17
Ans: (c)
Sol: Subsequence: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Subarray: A subarray of n-element array is an array composed from a contiguous block of the original array's elements.
Question is asking for subsequence.

What does    mean? It means you start from index i and go till index j with unit increment each time.
Ultimately they are asking 'Maximum subarray sum'.

sum = 6 + 3 - 1 - 2 + 13 + 4 - 9 - 1 + 4 + 12 = 29

Q2: Given below are some algorithms, and some algorithm design paradigms.

Match the above algorithms on the left to the corresponding design paradigm they follow.  (2015 SET-2)
(a) 1-i, 2-iii, 3-i, 4-v
(b) 1-iii, 2-iii, 3-1, 4-v
(c) 1-iii, 2-ii, 3-1, 4-iv
(d) 1-iii, 2-ii, 3-i, 4-v
Ans: (c)
Sol: Dijkstra's Shortest path algorithm uses greedy design (always choosing the shortest neighbour) while Floyd Warshall Algorithm to compute all shortest paths uses Dynamic Programming.
Binary search uses Divide and Conquer (though we eliminate one part at each time) and Back tracking traversal to a graph uses Depth First Search (DFS) (in DFS we have to backtrack to a node after searching through all its descendant nodes if the searched node is not found).

Q3: Match the following:   (2015 SET-1)

(a) P-iii, Q-ii, R-iv, S-i
(b) P-i, Q-ii, R-iv, S-iii
(c) P-ii, Q-iii, R-iv, S-i
(d) P-ii, Q-i, R-iii, S-iv
Ans: (c)
Sol: 
Prim's algo. always chooses minimum adj. edge using greedy technique.
Floyd is a dynamic programming technique.
Merge is a divide & conquer as we first divide the given array till single element and then merge them in single sorted array.
Hamiltonian uses back tracking.
P-2
Q-3
R-4
S-1

Q4: The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.  (2014 SET-1)
(a) 100
(b) 99
(c) 198
(d) 148
Ans: (d)
Sol: We can solve this question by using Tournament Method Technique -
1. To find the smallest element in the array will take n - 1 comparisons = 99.
2. To find the largest element -
a. After the first round of Tournament, there will be exactly n/2 numbers = 50 that will loose the round.
b. So, the biggest looser (the largest number) should be among these 50 loosers.
To find the largest number will take n/2 - 1 comparisons = 49.
Total 99 + 49 = 148.

Q5: If n is a power of 2, then the minimum number of multiplications needed to compute aⁿ is  (1999)
(a) log₂ n
(b) √n
(c) n-1
(d) n
Ans: (a)
Sol: aⁿ = (a²)^n/2.
One multiplication and recurrence on n/2. So, we get the recurrence relation for the number of multiplications as
T(n) = T(n/2) + 1.
This gives T(n) = log₂n.
For n = 8, we can do
b = a x a
b = b x b
b = b x b and we get b = a⁸.