Consider a table $T$, where the elements $T[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] = 1 \quad \text{for } k = 0,1,2, \dots, n$$ $$T[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 $T$. Assume that for both the algorithms, for all $0 \le i, j \le n$, $T[i][j]$ has been initialized to 1. Algorithm $B_1$: For $i = 1, 2, \dots, n$ $\qquad\qquad\qquad$ For $j = 1, 2, \dots, n$ $\qquad\qquad\qquad\qquad T[i][j] = 2T[i - 1][j] + 3T[i][j - 1]$ Algorithm $B_2$: For $s = 2, 3, \dots, 2n$ $\qquad\qquad\qquad$ For $i = 1, 2, \dots, n$ $\qquad\qquad\qquad\qquad$ For $j = 1, 2, \dots, n$ $\qquad\qquad\qquad\qquad\qquad$ If $(i + j == s)$ $\qquad\qquad\qquad\qquad\qquad\qquad T[i][j] = 2T[i - 1][j] + 3T[i][j - 1]$ 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 \le i, j \le 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?

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