Divide And Conquer – GATE CSE AlgorithmsPractice Questions & PYQs

This is the maximum subarray sum problem. We can use Kadane's algorithm to find the solution. We iterate through the array, maintaining the maximum sum of a subarray ending at the current position.
The subarray with the maximum sum starts at index 2 (value 6) and ends at index 11 (value 12).
The subarray is [6, 3, -1, -2, 13, 4, -9, -1, 4, 12].
The sum of these elements is $6+3-1-2+13+4-9-1+4+12 = 29$.

(P) Prim's algorithm for minimum spanning tree: This algorithm builds a minimum spanning tree by always choosing the next edge with the lowest weight that connects a visited vertex to an unvisited vertex. Making the locally optimal choice at each step makes this a (ii) Greedy method.

(Q) Floyd-Warshall algorithm for all pairs shortest paths: This algorithm finds the shortest paths between all pairs of vertices by breaking the problem down into smaller, overlapping subproblems (paths using a subset of intermediate vertices) and storing their solutions in a matrix. This bottom-up approach is a classic example of (iii) Dynamic programming.

(R) Mergesort: This sorting algorithm works by continuously splitting an array in half until it cannot be divided further, sorting those halves, and then merging them back together. This recursive splitting and merging is the definition of (iv) Divide and conquer.

(S) Hamiltonian circuit: Finding a path that visits every vertex in a graph exactly once and returns to the start is an NP-complete problem. The standard way to solve it systematically is by exploring possible paths and abandoning them (going back a step) as soon as it determines the current path cannot lead to a valid circuit. This is known as (i) Backtracking.

The matching of algorithms to their design paradigms is as follows:

• P. Dijkstra's Shortest Path algorithm makes the locally optimal choice at each step, which is a characteristic of the Greedy design (iii).
• Q. Floyd-Warshall algorithm builds up a solution by solving smaller subproblems, storing their results to avoid recomputation, which is the essence of Dynamic Programming (ii).
• R. Binary search works by repeatedly dividing the search interval in half, a classic example of Divide and Conquer (i).
• S. Backtracking search explores a potential solution path and backtracks when it hits a dead end, which is a form of Depth-first search (iv).

To find both the minimum and maximum of $n$ numbers, we can use a tournament approach.

1. Compare numbers in pairs. For $n$ numbers, this requires $n/2$ comparisons, resulting in $n/2$ "winners" (potential maximums) and $n/2$ "losers" (potential minimums).
2. Find the maximum among the $n/2$ winners. This requires $(n/2) - 1$ comparisons.
3. Find the minimum among the $n/2$ losers. This requires $(n/2) - 1$ comparisons.

For $n=100$:

1. Pairwise comparisons: $100/2 = 50$ comparisons.
2. Find maximum from 50 winners: $50 - 1 = 49$ comparisons.
3. Find minimum from 50 losers: $50 - 1 = 49$ comparisons.

Total comparisons = $50 + 49 + 49 = 148$.

Alternatively, an algorithm compares the first two elements to establish initial min and max (1 comparison). Then, it processes the remaining elements in pairs, comparing each pair (1 comparison). The smaller of the pair is compared with the current min (1 comparison), and the larger of the pair is compared with the current max (1 comparison).
For $n=100$:
Initial min/max: 1 comparison for first two elements.
Remaining $n-2 = 98$ elements, processed in $98/2 = 49$ pairs.
Each pair needs 3 comparisons (1 for the pair, 1 for min, 1 for max). So, $49 \times 3 = 147$ comparisons.
Total comparisons = $1 + 147 = 148$.

To compute $a^n$ where $n = 2^k$, we use the method of exponentiation by squaring. Starting with $a$, we calculate the sequence of powers: $a^2, a^4, a^8, \dots, a^{2^k} = a^n$. Each term in this sequence is obtained by squaring the previous term, requiring exactly one multiplication: $a^{2^i} = a^{2^{i-1}} \cdot a^{2^{i-1}}$. Since we need to reach $a^{2^k}$ from $a^1$, we perform this operation $k$ times. Because $k = \log_2 n$, the minimum number of multiplications is $\log_2 n$.

Using Master Theorem: a=2, b=2, f(n)=n → case 2 ⇒ T(n)=O(n log n).

Combine step merges the solutions of subproblems.

Merge Sort divides the array and recursively sorts subarrays before merging.

Worst case occurs when pivot divides array unevenly, leading to T(n)=T(n−1)+n ⇒ O(n^2).

Strassen reduces multiplication count ⇒ O(n^2.81).

Using Master Theorem case 2 extension ⇒ T(n)=O(n log^2 n).

Case 2 applies when f(n)=Θ(n^log_b a), giving T(n)=Θ(n^log_b a log n).

Worst case splits into n-1 and 0 ⇒ T(n)=T(n-1)+n.

(A) TRUE: Any element is found in at most $\lfloor \log_2 n \rfloor + 1$ comparisons - the worst case. (B) TRUE: The recursive binary search makes $O(\log n)$ recursive calls, each adding a frame to the call stack. Space $= O(\log n)$. (C) TRUE: The iterative version uses only variables (low, high, mid) - $O(1)$ stack space. (D) FALSE: Binary search on a sorted linked list is $O(n)$ time, not $O(\log n)$, because accessing the middle node requires $O(n/2)$ pointer traversals - random access is not available.

The recurrence is $T(n) = 2T(n/2) + 2$. Using Master Theorem or solving directly, we get $T(n) = \frac{3n}{2} - 2$, which is $\Theta(n)$.

Using the recursion tree method, the sum of work at each level decreases geometrically: $n + 7n/8 + (7/8)^2n dots$. This is a geometric series sum which converges to $O(n)$.

The maximum number of comparisons in binary search occurs when the element is not present in the array (unsuccessful search). In this case, binary search exhausts the entire search space before concluding the element is absent, performing $\lfloor \log_2 n \rfloor + 1$ comparisons. For elements present in the array, the search may terminate earlier (e.g., finding the middle element in just 1 comparison).

By substituting $n = 2^m$, the recurrence becomes $S(m) = 2S(m/2) + 1$. This solves to $S(m) = Theta(m)$. Replacing $m$ back with $log n$, we get $T(n) = Theta(log n)$.

(A) TRUE: Binary search relies on the sorted order to decide which half to search next - if the array is unsorted, binary search gives incorrect results. (B) TRUE: Binary search computes the middle index and accesses $A[\text{mid}]$ directly - this requires $O(1)$ random access. It is inefficient on linked lists for this reason. (C) FALSE: Binary search works correctly even with duplicate elements (though it may not find a specific occurrence). (D) FALSE: Binary search works on arrays of any size, not just powers of 2.

The recurrence is $T(n) = 3T(n/3) + O(n)$. By Master Theorem, this is $O(n \log_3 n)$.
Since $\log_3 n = \frac{\log_2 n}{\log_2 3}$, the complexity remains $O(n \log n)$.