GATE CS 2026 Set 2 Q.39: Dynamic Programming

Consider a table $T$ , where the elements $T[i][j]$ , $0 \le i, j \le 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:

T[0][k] = T[k][0] = 1 \quad \text{for } k = 0,1,2,\dots,n

T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] \quad \text{for } 1 \le i, j \le n

Consider the following two algorithms to compute entries of $T$ . Assume that for both the algorithms, for all $0 \le i, j \le n$ , $T[i][j]$ has been initialized to $1$ .

Algorithm B1:
For i = 1, 2, ..., n
    For j = 1, 2, ..., n
        T[i][j] = 2*T[i - 1][j] + 3*T[i][j - 1]

Algorithm B2:
For s = 2, 3, ..., 2n
    For i = 1, 2, ..., n
        For j = 1, 2, ..., n
            If (i + j == s)
                T[i][j] = 2*T[i - 1][j] + 3*T[i][j - 1]

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 \le i, j \le 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?

Both algorithms $B_1$ and $B_2$ are correct

Algorithm $B_1$ is correct, but algorithm $B_2$ is incorrect

Algorithm $B_2$ is correct, but algorithm $B_1$ is incorrect

Both algorithms $B_1$ and $B_2$ are incorrect

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Check whether the dependencies $T[i-1][j]$ and $T[i][j-1]$ are already computed before $T[i][j]$ in both row-major order ( $B_1$ ) and anti-diagonal order ( $B_2$ ).

To compute $T[i][j]$ ( $i, j \ge 1$ ), only $T[i-1][j]$ and $T[i][j-1]$ are needed:

In Algorithm $B_1$ (row-major order), when at $(i, j)$ , row $i-1$ has already been completed (giving $T[i-1][j]$ ) and column $j-1$ in row $i$ has just been completed (giving $T[i][j-1]$ ).
In Algorithm $B_2$ (anti-diagonal order by $s = i + j$ ), both dependencies $(i-1, j)$ and $(i, j-1)$ have index sum $(i + j) - 1 = s - 1$ , so they were already computed during the previous outer-loop iteration $s - 1$ (or initialized at $s - 1 \le 1$ ).

Therefore, both algorithms $B_1$ and $B_2$ respect the DAG of subproblem dependencies and are correct.

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 39 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source