GateAI
Dynamic Programming

GATE CSE 2026 Set 2 · Q39

MCQ2 marksMedium

Time

Consider a table TT, where the elements T[i][j],0≤i,j≤nT[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]=1for k=0,1,2,…,nT[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]for 1≤i,j≤nT[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 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 B1B_1: For i=1,2,…,ni = 1, 2, \dots, n \qquad\qquad\qquad For j=1,2,…,nj = 1, 2, \dots, n T[i][j]=2T[i−1][j]+3T[i][j−1]\qquad\qquad\qquad\qquad T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] Algorithm B2B_2: For s=2,3,…,2ns = 2, 3, \dots, 2n \qquad\qquad\qquad For i=1,2,…,ni = 1, 2, \dots, n \qquad\qquad\qquad\qquad For j=1,2,…,nj = 1, 2, \dots, n \qquad\qquad\qquad\qquad\qquad If (i+j==s)(i + j == s) T[i][j]=2T[i−1][j]+3T[i][j−1]\qquad\qquad\qquad\qquad\qquad\qquad T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] Algorithm Bk,k∈{1,2}B_k, 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?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) Both algorithms B1 and B2 are correct

Dynamic Programming

To verify the correctness of each algorithm, we check whether the subproblem dependencies are computed before they are used.

The recurrence relation is:

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

Thus, computing T[i][j]T[i][j] requires the values of T[i−1][j]T[i - 1][j] and T[i][j−1]T[i][j - 1].

  1. Algorithm B1B_1:

    • Traverses the table in standard row-major order (ii from 11 to nn, then jj from 11 to nn).

    • When evaluating cell (i,j)(i, j):

      • T[i−1][j]T[i - 1][j] belongs to the previous row i−1i - 1, which has already been fully computed.

      • T[i][j−1]T[i][j - 1] belongs to the current row at column j−1j - 1, which was computed in the immediately preceding iteration of the inner loop.

    • Therefore, all dependencies are available, so Algorithm B1B_1 is correct.

  2. Algorithm B2B_2:

    • Iterates over the anti-diagonal index sum s=i+js = i + j from 22 to 2n2n.

    • For a cell (i,j)(i, j) where i+j=si + j = s:

      • The dependency T[i−1][j]T[i - 1][j] has index sum (i−1)+j=s−1(i - 1) + j = s - 1.

      • The dependency T[i][j−1]T[i][j - 1] has index sum i+(j−1)=s−1i + (j - 1) = s - 1.

    • Since the outer loop increments ss monotonically, all entries with index sum s−1s - 1 are completely evaluated before any entry with index sum ss is processed.

    • Therefore, both dependencies are already correctly computed, so Algorithm B2B_2 is correct.

Thus, both algorithms B1B_1 and B2B_2 are correct, corresponding to option (A).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Dynamic Programming previous year question is Q39 of the GATE CSE 2026 Set 2 paper. Find more GATE CSE PYQs on Dynamic Programming in Algorithms, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Dynamic Programming PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Dynamic Programming in GATE CSE

Dynamic Programming has 7 GATE CSE PYQs across 6 papers from 2011 to 2026. This is the only 2-mark MCQ among them, and it is the only one in GATE CSE 2026 Set 2.

How GATE tests Dynamic Programming

More from GATE CSE 2026 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2026 Set 2 · Q39 · MCQ

Consider a table T, where the elements T[i][j], 0 ≤ i, j ≤ 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, , n T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] for 1 ≤ i, j ≤ n Consider the following two algorithms to compute entries of T. Assume that for both the algorithms, for all 0 ≤ i, j ≤ n, 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 Bk, k ∈ {1,2} is said to be correct if and only if it calculates the correct values of T[i][j], for all 0 ≤ i, j ≤ n, (as per the recursive formulation) at the end of the execution of the algorithm Bk. Which one of the following statements is true?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.