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?
T[0][π]=π[π][0]=1 for π=0,1,2,β¦,π
T[π][π]=2π[πβ1][π]+ 3π[π][πβ1] for 1β€π,πβ€π

Correct : a
Similar Questions
Match the following
(P) Primβs algorithm for minimum spanning tree
(i) Backtracking
(Q) Floyd-Warshall algorithm fo...
Consider the following table
Algorithms
Design Paradigms
(P) Kruskal
(i) Divide and Conquer...
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...
Total Unique Visitors
Loading......