Success TrackerSuccess Tracker
Log inSign up

GATE CS 2026 Set 2 — Question 39

Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.
MCQ+2 / -0.67MediumMemoization vs TabulationDynamic ProgrammingAlgorithms

Algorithms → Dynamic Programming → Memoization vs Tabulation

Last updated

Question

Consider a table TT, where the elements T[i][j],0≤i,j≤nT[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]=1for k=0,1,2,...,nT[0][k] = T[k][0] = 1 \quad \text{for } k = 0,1,2, ..., nT[i][j]=2T[i−1][j]+3T[i][j−1]for 1≤i,j≤nT[i][j] = 2T[i-1][j] + 3T[i][j-1] \quad \text{for } 1 \le i, j \le nConsider the following two algorithms to compute entries of TT. Assume that for both the algorithms, for all 0≤i,j≤n0 \le i, j \le n, T[i][j]T[i][j] has been initialized to 1.
Algorithm B1B_1:
For i = 1, 2, ..., n
    For j = 1, 2, ..., n
        T[i][j] = 2T[i-1][j] + 3T[i][j-1]
Algorithm B2B_2:
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 Bk,k∈{1,2}B_k, k \in \{1,2\} is said to be correct if and only if it calculates the correct values of T[i][j]T[i][j], for all 0≤i,j≤n0 \le i, j \le n, (as per the recursive formulation) at the end of the execution of the algorithm BkB_k.
Which one of the following statements is true?
Your answer

Choose one option, then check your answer.

The solution stays hidden until you check.

Continue learning with Success Tracker

A step still unclear? Work through it with support

Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.

AI-powered practice· Unlimited practice on eligible plans
PYQs with solutions
Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
Practice that adapts
Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
AI doubt support
Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.

Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.

Start with a free accountView plans and allowances

This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.

More questions on Dynamic Programming

2026 Set 1 Q17Consider the following recurrence relations: For all n>1n > 1,…2026 Set 2 Q24Consider the following functions, where nn is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array A=[10,7,8,19,41,35,25,31]A = [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort algorithm is…2026 Set 2 Q37Let GG be a weighted directed acyclic graph with mm edges and nn vertices. Given GG and a…