T[0][𝑘]=𝑇[𝑘][0]=1 for 𝑘=0,1,2,…,𝑛
T[𝑖][𝑗]=2𝑇[𝑖−1][𝑗]+ 3𝑇[𝑖][𝑗−1] for 1≤𝑖,𝑗≤𝑛

Correct : a
The correct answer is Option A — Both algorithms B₁ and B₂ are correct.
To verify correctness, we must confirm that for each algorithm, whenever T[i][j] is computed, its two dependencies — T[i−1][j] (row above, same column) and T[i][j−1] (same row, previous column) — have already been correctly computed.
Algorithm B₁ — Row-by-row, left-to-right: The outer loop iterates over rows i = 1 to n, and the inner loop over columns j = 1 to n. When T[i][j] is about to be computed, T[i−1][j] belongs to row i−1, which was fully computed in an earlier outer iteration. T[i][j−1] belongs to the current row but was computed at the previous j step in the inner loop. Both dependencies are satisfied in the correct order. B₁ is correct.
Algorithm B₂ — Anti-diagonal order: The outer loop iterates over the anti-diagonal sum s = i+j, from 2 to 2n. All cells with i+j = s are computed together in one pass. When T[i][j] (with i+j = s) is being computed: T[i−1][j] has index sum (i−1)+j = s−1, belonging to the previous anti-diagonal. T[i][j−1] has index sum i+(j−1) = s−1, also on the previous anti-diagonal. Since s−1 < s, both dependencies were fully computed before the current diagonal s is processed. B₂ is correct.
The key insight is that the recurrence T[i][j] = 2T[i−1][j] + 3T[i][j−1] requires dependencies that lie either on the previous row (i−1) or the previous column position (j−1). Both row-major order (B₁) and anti-diagonal order (B₂) satisfy this dependency constraint, making both algorithms valid bottom-up DP traversal strategies.
Similar Questions
Total Unique Visitors