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

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

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......