Question

Consider a table 𝑇, where the elements 𝑇[𝑖][𝑗], 0 ≤𝑖, 𝑗≤𝑛, 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:
𝑇[0][𝑘] = 𝑇[𝑘][0] = 1 for 𝑘= 0,1,2, … , 𝑛
𝑇[𝑖][𝑗] = 2𝑇[𝑖−1][𝑗] + 3𝑇[𝑖][𝑗−1] for 1 ≤𝑖, 𝑗≤𝑛
Consider the following two algorithms to compute entries of 𝑇. Assume that for
both the algorithms, for all 0 ≤𝑖, 𝑗≤𝑛, 𝑇[𝑖][𝑗] 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 𝐵𝑘, 𝑘∈{1,2} is said to be correct if and only if it calculates the correct
values of 𝑇[𝑖][𝑗], for all 0 ≤𝑖, 𝑗≤𝑛, (as per the recursive formulation) at the end
of the execution of the algorithm 𝐵𝑘.
Which one of the following statements is true?

• A. Both algorithms 𝐵1 and 𝐵2 are correct
• B. Algorithm 𝐵1 is correct, but algorithm 𝐵2 is incorrect
• C. Algorithm 𝐵2 is correct, but algorithm 𝐵1 is incorrect
• D. Both algorithms 𝐵1 and 𝐵2 are incorrect

Hint:

Both algorithms only ever use \(T[i-1][j]\) and \(T[i][j-1]\) after those entries are finalized -- B1 via row-major order, B2 via increasing diagonal sum \(i+j\) -- so both compute the table correctly.

Answer 1

The Correct Option is A

Step 1: Picture the table \(T\) as a grid where each cell \((i,j)\) needs its left neighbor \((i,j-1)\) and its top neighbor \((i-1,j)\) to already be finalized. Any traversal order that respects this 'left-and-top-before-me' rule will compute the table correctly.
Step 2: Algorithm \(B1\) fills the grid row by row, and within each row, column by column. When cell \((i,j)\) is reached, the entire row \(i-1\) is already done (finished in the prior outer loop pass) and all cells to the left in row \(i\) are already done (finished earlier in the same pass). So both required neighbors are ready -- \(B1\) respects the dependency rule everywhere.
Step 3: Algorithm \(B2\) instead fills the grid by anti-diagonals, that is, all cells whose row plus column equals a fixed value \(s\), taking \(s\) from small to large. For a cell \((i,j)\) on diagonal \(s = i+j\), its top neighbor \((i-1,j)\) and left neighbor \((i,j-1)\) both lie on diagonal \(s-1\), which is processed strictly before diagonal \(s\). So \(B2\) also respects the same dependency rule, just via a different sweep pattern.
Step 4: Since dependency correctness is the only requirement for the dynamic programming table to be filled properly, and both traversal orders (row-major for \(B1\), diagonal for \(B2\)) never reference an unfinished cell, neither algorithm can produce a wrong entry.
Step 5: Hence both computed tables match the recursive definition exactly, meaning both \(B1\) and \(B2\) are correct implementations.
Final Answer: Both algorithms \(B_1\) and \(B_2\) are correct