Computer Sciences > GATE 2026 SET-2 > Algorithms
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:
T[0][𝑘]=𝑇[𝑘][0]=1       for 𝑘=0,1,2,…,𝑛
T[𝑖][𝑗]=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 𝐵𝑘,𝑘∈{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 B₁ and B₂ are correct
B
Algorithm B₁ is correct, but algorithm B₂ is incorrect
C
Algorithm B₂ is correct, but algorithm B₁ is incorrect
D
Both algorithms B₁ and B₂ are incorrect

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

Match the following (P) Prim’s algorithm for minimum spanning tree (i) Backtracking (Q) Floyd-Warshall algorithm fo...
#82 MCQ
Consider the following table Algorithms Design Paradigms (P) Kruskal (i) Divide and Conquer...
#203 MCQ
Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Let f1(n) and f2(n) denote the number of times the statement "x = x + 1" is...
#989 MSQ

Related Topics

dynamic programming table correctness GATE 2026 GATE CS 2026 Set-2 Q39 bottom-up DP traversal order GATE anti-diagonal DP filling GATE row major DP computation GATE algorithm correctness recurrence GATE 2026 DP table dependency order GATE CSE

Unique Visitor Count

Total Unique Visitors

Loading......