A sub-sequence of a given sequence is just the given sequence with some…
2009
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X [m] and Y [n] of lengths m and n, respectively, with indexes of X and Y starting from 0.
Consider the data given in the previous question. The values of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m+1 and N =n+1, such that L[i, j] = l(i, j).
Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?
- A.
All elements L should be initialized to 0 for the values of l(i,j) to be properly computed
- B.
The values of l(i,j) may be computed in a row major order or column major order of L(M,N)
- C.
The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N)
- D.
L[p,q] needs to be computed before L[r,s] if either p < r or q < s.
Attempted by 103 students.
Show answer & explanation
Correct answer: B
Correct statement: The values may be computed in a row-major order or column-major order of the table.
Key initialization: Set the first row and the first column to zero: L[i][0] = 0 for 0 ≤ i ≤ m and L[0][j] = 0 for 0 ≤ j ≤ n. These are the base cases for the recurrence.
Table size: Use an (m+1)×(n+1) table L where L[i][j] stores l(i,j).
Recurrence: For i ≥ 1 and j ≥ 1, if X[i-1] = Y[j-1] then L[i][j] = L[i-1][j-1] + 1; otherwise L[i][j] = max(L[i-1][j], L[i][j-1]).
Computation orders that work: Row-major (process rows from i=1..m and within each row process j=1..n left-to-right) works because each L[i][j] needs L[i-1][j] (previous row) and L[i][j-1] (earlier in same row) which will be available. Column-major (process columns from j=1..n and within each column process i=1..m top-to-bottom) also works for analogous reasons.
Complexity: Time and space are Θ(mn) for the full table.
Why the other statements are wrong:
Initializing every entry of the table to zero is incorrect because non-base entries must be computed from the recurrence; setting them all to zero would overwrite computed values and yield an incorrect result.
Claiming that neither row-major nor column-major computation works is false because both traversal orders respect the direct dependencies of each cell (top, left, diagonal).
The assertion that any cell with a strictly smaller row index or strictly smaller column index must be computed before another cell is too broad. A cell only directly depends on its immediate top, left, and top-left neighbors; correct traversals ensure those are available when needed.
A video solution is available for this question — log in and enroll to watch it.