GATE 2026 CS2 Q.39: solution and answer

GATE 2026 · CS2Q.39 · 2 marks · MCQ

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:

$T [0] [k] = T [k] [0] = 1 for k = 0, 1, 2, \dots, n$
$T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1] for 1 \leq i, j \leq n$

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, ..., n
    For j = 1, 2, ..., n
        T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm $B_{2}$ :

For s = 2, 3, ..., 2n
    For i = 1, 2, ..., n
        For j = 1, 2, ..., n
            If (i + j == s)
                T[i][j] = 2T[i-1][j] + 3T[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 \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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct answer is (A): both algorithms $B_{1}$ and $B_{2}$ correctly compute every entry of the table $T$ .

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

The recurrence for interior cells is $T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1]$ for $1 \leq i, j \leq n$ , and every cell with $i = 0$ or $j = 0$ is a boundary value fixed at $1$ by $T [0] [k] = T [k] [0] = 1$ . Neither algorithm's loop body ever touches a boundary cell (both inner loops range over $i, j$ from $1$ to $n$ ), so the boundary values stay correct throughout.
Algorithm $B_{1}$ (row-major: $i = 1, \dots, n$ outer, $j = 1, \dots, n$ inner). Fix a row $i$ . By induction on $j$ : $T [i] [0] = 1$ is the correct boundary value and is never overwritten before $T [i] [1]$ is computed. When $T [i] [j]$ is computed, $T [i] [j - 1]$ was computed earlier in the same row's $j$ -loop (since $j - 1 < j$ ) and is therefore already correct by the induction hypothesis, and $T [i - 1] [j]$ was computed and finalized during the previous row's iteration (row $i - 1$ is fully completed before row $i$ starts) and is also correct. So every $T [i] [j]$ is computed from two already-correct values. By induction over $i$ (rows) and $j$ (columns within a row), $B_{1}$ computes every entry correctly.
Algorithm $B_{2}$ (anti-diagonal: outer loop $s = 2, \dots, 2 n$ , inner loops scan all $(i, j)$ and update those with $i + j = s$ ). A cell $(i, j)$ with $i + j = s$ depends only on $(i - 1, j)$ , whose index sum is $s - 1$ , and $(i, j - 1)$ , whose index sum is also $s - 1$ . Every cell with index sum $s - 1$ is updated during a strictly earlier outer iteration ( $s - 1 < s$ ) and is therefore already correct by induction on $s$ (base case $s = 2$ : dependencies have sum $1$ , i.e. $T [0] [1]$ or $T [1] [0]$ , both untouched boundary values equal to $1$ ).
Within one fixed $s$ , the cells satisfying $i + j = s$ (e.g., for $s = 4$ : $(1, 3), (2, 2), (3, 1)$ ) never depend on each other — each one's two dependencies always lie on diagonal $s - 1$ , never on diagonal $s$ itself. So the order in which $i, j$ are scanned inside a fixed $s$ is irrelevant to correctness; every cell on diagonal $s$ is computed only from already-finalized diagonal- $(s - 1)$ (or boundary) values. By induction over $s$ , $B_{2}$ computes every entry correctly.
Both $B_{1}$ 's row-major order and $B_{2}$ 's anti-diagonal order are valid topological orders of the dependency DAG in which $T [i] [j]$ depends only on $T [i - 1] [j]$ and $T [i] [j - 1]$ (each strictly decreasing $i + j$ by 1). Neither algorithm ever reads a cell before the cell it depends on has been finalized, so both algorithms are correct.
This matches option (A): both algorithms $B_{1}$ and $B_{2}$ are correct.

KEY IDEA

Whenever a DP recurrence's dependencies always come from strictly "smaller" cells in some measure (here, $i + j$ strictly decreases by 1 at each dependency), any loop order that is a valid topological order of that dependency structure computes the table correctly — row-major and anti-diagonal ("wavefront") order are both such valid orders here, since each cell's two dependencies fall on the immediately preceding row/column or the immediately preceding diagonal, never on the same diagonal.

WATCH OUT FOR

Assuming that scanning order only matters when it visits cells "out of the usual row/column order," and therefore either (a) wrongly flagging $B_{2}$ as incorrect on the intuition that its triple-nested loop with an if condition looks unusual or wasteful, without checking that its dependencies are actually satisfied, or (b) failing to verify that cells sharing the same diagonal ( $i + j = s$ ) never depend on each other, which is the fact that makes the inner scan order inside a fixed $s$ harmless.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes

GATE 2026 CS2 Q.39: solution and answer

Answer and solution

More Design techniques questions