GATE CS 2026 (Afternoon) — Question 39

AlgorithmsDynamic Programming InfrastructureMCQ2 marks · −2/3 if wrongHard

Consider a table \( T \), where the elements \( T[i][j], 0 \le i, j \le 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, \dots, n \) \( T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] \) for \( 1 \le i, j \le n \) Consider the following two algorithms to compute entries of \( T \). Assume that for both the algorithms, for all \( 0 \le i, j \le n \), \( T[i][j] \) has been initialized to 1. Algorithm \( B_1 \): For \( i = 1, 2, \dots, n \) For \( j = 1, 2, \dots, n \) \( T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] \) Algorithm \( B_2 \): For \( s = 2, 3, \dots, 2n \) For \( i = 1, 2, \dots, n \) For \( j = 1, 2, \dots, n \) If \( (i + j == s) \) \( T[i][j] = 2T[i - 1][j] + 3T[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 \le i, j \le 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?
  1. A
    Both algorithms \( B_1 \) and \( B_2 \) are correct
  2. B
    Algorithm \( B_1 \) is correct, but algorithm \( B_2 \) is incorrect
  3. C
    Algorithm \( B_2 \) is correct, but algorithm \( B_1 \) is incorrect
  4. D
    Both algorithms \( B_1 \) and \( B_2 \) are incorrect
Practise the full 2026-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Dynamic Programming InfrastructureTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group