Divide And Conquer – GATE CSE AlgorithmsPractice Questions & PYQs

Worst-case comparisons $= \lfloor \log_2 1000 \rfloor + 1$. $\log_2 1000 = \log_2 (2^{10}) \times (1000/1024) \approx 9.97$. So $\lfloor \log_2 1000 \rfloor = 9$. Worst case $= 9 + 1 = \mathbf{10}$ comparisons. Verification: $2^9 = 512 < 1000 \leq 1024 = 2^{10}$, confirming $\lfloor \log_2 1000 \rfloor = 9$.

To count occurrences of $k$: (1) Use binary search to find the leftmost (first) occurrence of $k$ - $O(\log n)$. (2) Use binary search to find the rightmost (last) occurrence of $k$ - $O(\log n)$. Count $=$ (last index) $-$ (first index) $+ 1$, computed in $O(1)$. Total time $= O(\log n) + O(\log n) = O(\log n)$.

Merge sort always divides and merges, giving T(n)=2T(n/2)+n → Θ(n log n) in all cases.

A decision tree for searching $n$ elements has: $n$ internal nodes (successful searches - one per element found) and $n + 1$ leaves (unsuccessful searches - one for each gap between/around elements). Total leaves in a comparison tree for search $= 2n + 1$ (n successful + n+1 unsuccessful). A binary tree with $2n+1$ leaves has depth $\geq \lceil \log_2(2n+1) \rceil = \Omega(\log n)$. Hence any comparison-based search requires $\Omega(\log n)$ comparisons in the worst case.

Worst-case comparisons $= \lfloor \log_2 100 \rfloor + 1$. $2^6 = 64 < 100 \leq 128 = 2^7$, so $\lfloor \log_2 100 \rfloor = 6$. Worst case $= 6 + 1 = \mathbf{7}$ comparisons. Trace of search space: $100 \to 50 \to 25 \to 12 \to 6 \to 3 \to 1 \to$ not found (7 comparisons).

Using Master Theorem: a=2, b=2, log_b(a)=1. f(n)=n^0.5 which is O(n^(1-ε)) for ε=0.5, so Case 1 applies → T(n) = Θ(n).

Merge Sort, Quick Sort, and Binary Search all divide the problem into sub-problems. Dijkstra's algorithm is a Greedy algorithm.

Lower_bound finds the first position where $v$ can be inserted to maintain sorted order - equivalently, the index of the first element $\geq v$. In $A = [2, 5, 5, 8, 10, 15]$ (0-indexed): $A[0]=2 < 5$, $A[1]=5 \geq 5$. The first element $\geq 5$ is at index $\mathbf{1}$. Binary search trace: low=0, high=5, mid=2: $A[2]=5 \geq 5$, high=2. low=0, high=2, mid=1: $A[1]=5 \geq 5$, high=1. low=0, high=1, mid=0: $A[0]=2 < 5$, low=1. low=high=1 $\to$ return 1.

Searching for $65$ in $[10,20,30,40,50,60,70]$: Comparison 1: $\text{mid} = 4$, $A[4] = 40$. $65 > 40$, search right half $[50,60,70]$ (indices 5-7). Comparison 2: $\text{mid} = 6$, $A[6] = 60$. $65 > 60$, search right $[70]$ (index 7). Comparison 3: $\text{mid} = 7$, $A[7] = 70$. $65 < 70$, search left - low $>$ high, element not found. Total $= \mathbf{3}$ comparisons.

(A) TRUE: Exponential search doubles the index ($1, 2, 4, 8, \ldots$) until $A[i] \geq$ key - takes $O(\log p)$ steps; then binary search on $[i/2, i]$ also takes $O(\log p)$. Total $O(\log p)$. (B) TRUE: Interpolation search uses $\text{mid} = \text{low} + \frac{(\text{key} - A[\text{low}]) \times (\text{high} - \text{low})}{A[\text{high}] - A[\text{low}]}$ - on uniform data, average case $= O(\log \log n)$. (C) TRUE: Both are standard binary search variants - lower_bound finds first $\geq$ key, upper_bound finds first $>$ key, each in $O(\log n)$. (D) TRUE: Fibonacci search uses Fibonacci numbers to avoid division, with $O(\log n)$ worst-case comparisons - useful when division is expensive.

For a search that fails, the algorithm explores a path from the root to a leaf in the decision tree. The height of the tree is $lfloor log_2 n floor$, and the final comparison at the leaf makes it $+ 1$.

The recurrence is $T(n) = sqrt{n}T(sqrt{n}) + n$. Let $n = 2^m$. $T(2^m) = 2^{m/2}T(2^{m/2}) + 2^m$. Dividing by $2^m$: rac{T(2^m)}{2^m} = rac{T(2^{m/2})}{2^{m/2}} + 1. This solves to $O(log m)$, so $T(n) = n log log n$.

Activity Selection Problem is a classic Greedy algorithm problem, not Divide and Conquer.

Substitute $n = 2^m$. Then $T(2^m) = 2T(2^{m/2}) + 1$. Let $S(m) = T(2^m)$. $S(m) = 2S(m/2) + 1$. By Master Theorem, $S(m) = O(m)$. Since $m = log_2 n$, $T(n) = O(log n)$.

In binary search, at each step the search space is halved. Starting from $n$ elements, after $k$ comparisons the search space reduces to $n/2^k$. The search terminates when $n/2^k = 1$, i.e., $k = \log_2 n$. Hence the worst-case number of comparisons is $\lfloor \log_2 n \rfloor + 1 = O(\log n)$.

Binary search requires sorted data to divide the search space efficiently.

In the worst case, we compare elements until one array is exhausted. The last element of the remaining array doesn't need a comparison. Hence, $n + m - 1$.

a=3, b=2 ⇒ n^(log₂3) dominates ⇒ T(n)=O(n^log₂3).

(A) TRUE: Worst case is $\lfloor \log_2 n \rfloor + 1 = O(\log n)$ comparisons. (B) TRUE: Binary search needs $O(1)$ random access to compute $A[\text{mid}]$; linked lists require $O(n)$ traversal to find the middle. (C) FALSE: Binary search is not stable in the sense that with duplicates, it may return any occurrence of the key, not necessarily the first or last - depends on implementation. (D) TRUE: The iterative version uses only a few variables (low, high, mid) - $O(1)$ extra space. Recursive version uses $O(\log n)$ stack space.

In a binary search decision tree, the root is at level 1 (found in 1 comparison), its children at level 2 (found in 2 comparisons), and so on. If an element requires exactly 4 comparisons, it resides at level 4 of the decision tree. Verification: $2^{4-1} = 8$ elements are at level 4 (found in exactly 4 comparisons). For $n=64$ (height $= \log_2 64 = 6$), level 4 is well within the tree.