Skip to content
GATETECH
Official PYQ · 2026Set 2 · Q29Algorithm Design: Dynamic ProgrammingMCQ2 marks

GATE CS 2026 Set 2 Q29 — Algorithm Design: Dynamic Programming

Explain with AI

Consider a table TT, where the elements T[i][j],0≤i,j≤nT[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,…,nT[i][j]=2T[i−1][j]+3T[i][j−1] for 1≤i,j≤n\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 TT. Assume that for both the algorithms, for all 0≤i,j≤n,T[i][j]0 \leq i, j \leq n, T[i][j] has been initialized to 11.
Algorithm B1B_{1} : For i=1,2,…,ni=1,2, \ldots, n
 For j=1,2,…,nT[i][j]=2T[i−1][j]+3T[i][j−1]\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 B2:B_{2}: For s=2,3,…,2ns=2,3, \ldots, 2 n
 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]\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 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 \leq i, j \leq 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?

Choose one option
View worked solution

Answer: A

To determine the correctness of the algorithms, we need to analyze the dependency of the recurrence relation:

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

To compute the value at cell (i,j)(i, j), we must have already computed the values at:

  • Top neighbor: T[i−1][j]T[i-1][j]
  • Left neighbor: T[i][j−1]T[i][j-1]

1. Analysis of Algorithm B1B_1

Algorithm B1B_1 uses a standard row-by-row traversal:

  • The outer loop ii runs from 11 to nn.
  • The inner loop jj runs from 11 to nn.

When computing T[i][j]T[i][j]:

  • T[i−1][j]T[i-1][j] belongs to the previous row (i−1)(i-1), which has already been completely computed.
  • T[i][j−1]T[i][j-1] belongs to the same row ii but the previous column (j−1)(j-1), which has already been computed in the previous iteration of the inner loop.

Since both dependencies are satisfied, Algorithm B1B_1 is correct.

2. Analysis of Algorithm B2B_2

Algorithm B2B_2 groups the computations by the sum of indices s=i+js = i + j:

  • The outer loop ss runs from 22 to 2n2n.
  • The inner loops iterate over all (i,j)(i, j) pairs such that i+j==si + j == s.

When computing T[i][j]T[i][j] for a given sum ss:

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

Since the outer loop processes the sums in strictly increasing order (s=2,3,ext...,2ns = 2, 3, ext{...}, 2n), all cells with index sum s−1s-1 are guaranteed to be computed before we process any cell with index sum ss.

Thus, both dependencies are always satisfied, and Algorithm B2B_2 is correct.

Therefore, both algorithms B1B_1 and B2B_2 are correct.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Dynamic Programming questions