GATE CS 2011 Q25 — Algorithm Design: Dynamic Programming

To determine the correct paradigm, let's analyze the given recurrence relation and algorithm:

1. Subproblem Definition: Let $L_i$ be the length of the longest monotonically increasing sequence starting at index $i$.
2. Overlapping Subproblems & Optimal Substructure: The value of $L_i$ directly depends on the already computed value of $L_{i+1}$: $$L_i = \begin{cases} 1 + L_{i+1} & \text{if } A[i] < A[i+1] \\ 1 & \text{otherwise} \end{cases}$$ This demonstrates optimal substructure (the optimal solution to a larger problem incorporates the optimal solution to a smaller subproblem) and overlapping subproblems.
3. Computation: We compute the values of $L_i$ from right to left (starting from $i = n-2$ down to $0$) and store them in an array $L$. This bottom-up tabulation is the hallmark of the Dynamic Programming paradigm.

Complexity Analysis:

• The algorithm performs a single pass from $n-2$ down to $0$.
• At each step $i$, it does a constant number of operations ($O(1)$).
• Thus, the time complexity is $\Theta(n)$, which is linear.

Evaluating the Options:

• Option A: Correct. The algorithm uses the dynamic programming paradigm.
• Options B & C: Incorrect. Branch and bound is typically used for optimization problems in search spaces (like TSP or Knapsack) using a state-space tree, which is not the case here.
• Option D: Incorrect. Divide and conquer divides the problem into independent subproblems (like Merge Sort), whereas here the subproblems are overlapping and solved sequentially.