Skip to content
GATEiit

GATE CSE 2026 Session 2 Q39: Row-wise vs anti-diagonal order for filling a DP table

Question

Consider a table TT, where the elements T[i][j]T[i][j], 0≤i,j≤n0 \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]=1for k=0,1,2,…,nT[i][j]=2T[i−1][j]+3T[i][j−1]for 1≤i,j≤n\begin{aligned} T[0][k] &= T[k][0] = 1 && \text{for } k = 0, 1, 2, \ldots, n \\ T[i][j] &= 2T[i-1][j] + 3T[i][j-1] && \text{for } 1 \le i, j \le n \end{aligned}

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

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

Algorithm BkB_k, k∈{1,2}k \in \{1, 2\} is said to be correct if and only if it calculates the correct values of T[i][j]T[i][j], for all 0≤i,j≤n0 \le i, j \le n, (as per the recursive formulation) at the end of the execution of the algorithm BkB_k.

Which one of the following statements is true?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2026 final answer key)

Concept used: A DP fill order is valid if every entry's dependencies are computed before it.

First step: T[i][j]T[i][j] depends on T[i−1][j]T[i-1][j] and T[i][j−1]T[i][j-1]; check that both row-major order and increasing i+ji + j (anti-diagonal) order compute those first.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 2 questions →