GATEverse Practice, past papers & mock tests
GATE 2026 · CS2 - Afternoon
AlgorithmsDynamic ProgramminghardMCQ2 marks
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] = 2*T[i-1][j] + 3*T[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] = 2*T[i-1][j] + 3*T[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] = 2*T[i-1][j] + 3*T[i][j-1] Algorithm Bk, 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 ≤ 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?
Save your progress

Related Algorithms PYQs