GATE CSE 2026 | Set 2 | Question: 29

Question

Consider a table $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:

\[
\begin{array}{ll}
T[0][k]=T[k][0]=1 & \text { for } k=0,1,2, \ldots, n \\
T[i][j]=2 T[i-1][j]+3 T[i][j-1] & \text { for } 1 \leq i, j \leq n
\end{array}
\]
Consider the following two algorithms to compute entries of $T$. Assume that for both the algorithms, for all $0 \leq i, j \leq n, T[i][j]$ has been initialized to $1$.
Algorithm $B_{1}$ : For $i=1,2, \ldots, n$
\[
\begin{array}{l}
\text { For } j=1,2, \ldots, n \\
\qquad T[i][j]=2 T[i-1][j]+3 T[i][j-1]
\end{array}
\]
Algorithm $B_{2}:$ For $s=2,3, \ldots, 2 n$
\[
\begin{array}{l}
\text { For } i=1,2, \ldots, n \\
\qquad \begin{array}{l}
\text { For } j=1,2, \ldots, n \\
\qquad \text { If }(i+j==s) \\
\quad\quad\quad\quad T[i][j]=2 T[i-1][j]+3 T[i][j-1]
\end{array}
\end{array}
\]
Algorithm $B_{k}, k \in\{1,2\}$ is said to be correct if and only if it calculates the correct values of $T[i][j]$, for all $0 \leq i, j \leq n$, (as per the recursive formulation) at the end of the execution of the algorithm $B_{k}$.

Which one of the following statements is true?

• A. Both algorithms $B_{1}$ and $B_{2}$ are correct
• B. Algorithm $B_{1}$ is correct, but algorithm $B_{2}$ is incorrect
• C. Algorithm $B_{2}$ is correct, but algorithm $B_{1}$ is incorrect
• D. Both algorithms $B_{1}$ and $B_{2}$ are incorrect

Answer 1

The correct statement is A. Both algorithms $B_1$ and $B_2$ are correct.

To determine if a Dynamic Programming (DP) algorithm is correct, we must ensure that for every entry $T[i][j]$, the subproblems it depends on—$T[i-1][j]$ and $T[i][j-1]$—have already been computed and stored in the table.

---

Analysis of the Dependency

The recursive formula is:

$$T[i][j] = 2T[i-1][j] + 3T[i][j-1]$$

This means to calculate the cell at $(i, j)$, you need:

1. The cell directly above it: $(i-1, j)$

2. The cell directly to its left: $(i, j-1)$

---

Evaluating Algorithm $B_1$ (Row-major order)

Algorithm $B_1$ uses a nested loop where $i$ (rows) is the outer loop and $j$ (columns) is the inner loop.

• When computing $T[i][j]$, $T[i-1][j]$ was completed during the previous iteration of the outer loop.

• $T[i][j-1]$ was completed during the previous iteration of the inner loop.

• Conclusion: All dependencies are satisfied. $B_1$ is correct.

---

Evaluating Algorithm $B_2$ (Diagonal order)

Algorithm $B_2$ iterates through the sum of indices $s = i + j$, starting from $2$ up to $2n$.

• To compute $T[i][j]$, we need $T[i-1][j]$ and $T[i][j-1]$.

• For both of these dependencies, the sum of indices is $(i-1) + j = s-1$ and $i + (j-1) = s-1$.

• Since the outer loop $s$ moves from $2 \to 2n$, all cells with a sum of $s-1$ are guaranteed to be finished before the algorithm attempts any cell with a sum of $s$.

• Conclusion: All dependencies are satisfied. $B_2$ is correct.

---

Final Verdict

Since both the row-by-row approach and the diagonal-sum approach respect the data dependency of the recurrence relation, both algorithms will yield the correct table values.

Correct Option: A

 

Answer 2

Har DP question mein bas ye check karo:

Rule

Agar recurrence mein dependency hai:

dp [i][j] ← dp [i−1] [j], dp [i][j−1]

 

To valid orders:

•  Row-wise
•  Column-wise
•  Diagonal-wise (increasing i+j)

 

Hence, Opt. A is correct 

 

Agar dependency hoti

dp [i][j] ← dp [i+1][j]    

to row-wise top-to-bottom galat ho jata.

Kyuki future cell pe depend kar raha hai.