Question

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:

\[ 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 \leq i,j \leq n \]
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, ..., n
    For j = 1, 2, ..., n
        T[i][j] = 2*T[i-1][j] + 3*T[i][j-1]

Algorithm \(B_2\):

For s = 2, 3, ..., 2n
    For i = 1, 2, ..., n
        For j = 1, 2, ..., n
            If (i + j == s)
                T[i][j] = 2*T[i-1][j] + 3*T[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 \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?

• A. Both algorithms \(B_1\) and \(B_2\) are correct
• B. Algorithm \(B_1\) is correct, but algorithm \(B_2\) is incorrect
• C. Algorithm \(B_2\) is correct, but algorithm \(B_1\) is incorrect
• D. Both algorithms \(B_1\) and \(B_2\) are incorrect

Hint:

Check whether each algorithm always computes \(T[i-1][j]\) and \(T[i][j-1]\) before it computes \(T[i][j]\); B1 goes row by row and B2 goes diagonal by diagonal (\(i+j\) = constant).

Answer 1

The Correct Option is A

Step 1: Understand what a "correct" order of computation means here.
Each entry \(T[i][j]\) for \(1 \leq i,j \leq n\) depends on two other entries, \(T[i-1][j]\) and \(T[i][j-1]\). For an algorithm to compute \(T[i][j]\) correctly using the formula, both of these must already hold their final, correct values at the moment \(T[i][j]\) is computed. So the real question is whether each algorithm always visits cells in an order where a cell's two "inputs" are finished before the cell itself is processed.

Step 2: Check Algorithm \(B_1\) (row by row, i outer, j inner).
\(B_1\) computes \(T[i][j]\) in the order \(i=1,2,\dots,n\), and for each \(i\), \(j=1,2,\dots,n\). When it is about to compute \(T[i][j]\), the entry \(T[i-1][j]\) belongs to the previous row \(i-1\), which was fully completed in an earlier pass of the outer loop, so it is already correct. The entry \(T[i][j-1]\) belongs to the same row \(i\) but an earlier column \(j-1\), which was computed earlier in the current inner loop pass, so it is also already correct. Both dependencies are satisfied before use, so \(B_1\) computes every entry correctly.

Step 3: Check Algorithm \(B_2\) (diagonal by diagonal, using \(s=i+j\)).
\(B_2\) only updates \(T[i][j]\) when \(i+j=s\), for \(s\) increasing from 2 up to \(2n\). Notice that the two entries \(T[i][j]\) depends on, \(T[i-1][j]\) and \(T[i][j-1]\), both have their indices summing to \((i-1)+j = i+j-1 = s-1\) and \(i+(j-1) = s-1\) respectively. So both dependencies always lie on the diagonal \(s-1\), which is strictly smaller than the current diagonal \(s\), meaning they were already fully computed in an earlier pass of the outer \(s\) loop, before the current \(s\) began. Within one fixed value of \(s\), the different \((i,j)\) pairs updated (all with \(i+j=s\)) never depend on each other, since their dependencies always point to diagonal \(s-1\), so the order in which \(i\) and \(j\) are looped for a fixed \(s\) does not matter. So \(B_2\) also always finishes a cell's two dependencies before that cell is computed, and it also computes every entry correctly.

Step 4: Confirm the base cases are untouched.
Both algorithms only run their update for \(1 \leq i,j \leq n\), so the boundary values \(T[0][k]=T[k][0]=1\) are never overwritten by either algorithm; they stay at their initialized value of 1, which matches the recursive formulation's base case exactly, in both algorithms.

Step 5: Rule out the incorrect options with the reasoning above.
Since \(B_1\) processes strictly in increasing order of \(i\) and, within a row, increasing order of \(j\), and every dependency of \(T[i][j]\) has either a smaller \(i\) or the same \(i\) with smaller \(j\), \(B_1\) can never use a stale value; this rules out both options that claim \(B_1\) is incorrect. Since \(B_2\) processes strictly in increasing order of \(s=i+j\), and every dependency of a diagonal-\(s\) entry lies on diagonal \(s-1\), \(B_2\) can also never use a stale value; this rules out both options that claim \(B_2\) is incorrect. So neither algorithm is wrong.

Final Answer:
Both \(B_1\) and \(B_2\) always compute the entries of \(T\) in a valid dependency order, so both are correct. \[ \boxed{\text{Both algorithms } B_1 \text{ and } B_2 \text{ are correct (Option A)}} \]