Consider a table π, where the elements π[π][π], 0 β€ π,π β€ π, representβ¦
2026
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:
π[0][π] = π[π][0] = 1 for π = 0,1,2, β¦ , π
π[π][π] = 2π[π β 1][π] + 3π[π][π β 1] for 1 β€ π,π β€ n
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: For π = 1, 2, β¦ , π
For π = 1, 2, β¦ , π
π[π][π] = 2π[π β 1][π] + 3π[π][π β 1]
Algorithim B2 :for S:2,3......2n
For π = 1, 2, β¦ , π
For π = 1, 2, β¦ , π
If (π + π == π )
π[π][π] = 2π[π β 1][π] + 3π[π][π β 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 B1 and B2 are correct
- B.
Algorithm B1 correct, B2 incorrect
- C.
Algorithm B2 correct, B1 incorrect
- D.
Both incorrect
Attempted by 58 students.
Show answer & explanation
Correct answer: A
The recurrence relation depends on T[i-1][j] and T[i][j-1]. Both algorithms must ensure these values are computed before T[i][j].
Algorithm B1 iterates i from 1 to n, then j from 1 to n. When computing T[i][j], T[i-1][j] is from the previous row (already computed) and T[i][j-1] is from the current row (already computed). Thus, B1 is correct.
Algorithm B2 iterates S from 2 to 2n. Dependencies T[i-1][j] and T[i][j-1] have index sums S-1. Since S increases, values for S-1 are computed before S. Thus, B2 is also correct.
Conclusion: Both algorithms respect the dependency structure and compute the table correctly.