The GATE Grind

GATE 2026 CS (CS2) – Question 39

Algorithms · Dynamic Programming · 2 marks · Multiple choice

Consider a table $T$ where the entries $T[i][j]$, $0 \le i,j \le n$, represent costs of subproblems in a dynamic programming algorithm. The recursive formulation is
$$T[0][k]=T[k][0]=1 \text{ for } k=0,1,2,\dots,n$$
$$T[i][j]=2T[i-1][j]+3T[i][j-1] \text{ for } 1\le i,j\le n.$$
Assume all entries are initially 1.

Algorithm $B_1$: for $i=1,2,\dots,n$, for $j=1,2,\dots,n$, set $T[i][j]=2T[i-1][j]+3T[i][j-1]$.

Algorithm $B_2$: for $s=2,3,\dots,2n$, for $i=1,2,\dots,n$, for $j=1,2,\dots,n$, if $i+j=s$, set $T[i][j]=2T[i-1][j]+3T[i][j-1]$.

Algorithm $B_k$, $k\in\{1,2\}$, is said to be correct if it computes the correct values of $T[i][j]$ for all $0\le i,j\le n$. Which one of the following statements is true?

  1. Both algorithms $B_1$ and $B_2$ are correct.
  2. Algorithm $B_1$ is correct, but algorithm $B_2$ is incorrect.
  3. Algorithm $B_2$ is correct, but algorithm $B_1$ is incorrect.
  4. Both algorithms $B_1$ and $B_2$ are incorrect.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Both algorithms $B_1$ and $B_2$ are correct.

Explanation

In algorithm $B_1$, each entry $T[i][j]$ is computed after both $T[i-1][j]$ and $T[i][j-1]$ are already available, because the table is filled row by row from left to right. In algorithm $B_2$, entries are filled by increasing values of $i+j$, that is, anti-diagonal order. Since both dependencies of $T[i][j]$ lie on the previous anti-diagonal with sum $i+j-1$, they are also available. Hence both algorithms compute the table correctly. Therefore, option (A) is correct.