Q29

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:

$$\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 $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, \ldots, n$

$$\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 $B_{2}:$ For $s=2,3, \ldots, 2 n$

$$\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 $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?