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. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] != Y[j-1]
- A.
expr1 ≡ l(i-1, j) + 1
- B.
expr1 ≡ l(i, j-1)
- C.
expr2 ≡ max(l(i-1, j), l(i, j-1))
- D.
expr2 ≡ max(l(i-1,j-1),l(i,j))
Attempted by 103 students.
Show answer & explanation
Correct answer: C
Correct recursive definition: the length l(i,j) of the longest common subsequence of X[0..i-1] and Y[0..j-1] is
Base case: l(i,j) = 0 if i = 0 or j = 0.
Match case: if X[i-1] = Y[j-1], then l(i,j) = l(i-1, j-1) + 1.
Mismatch case: if X[i-1] ≠ Y[j-1], then l(i,j) = max(l(i-1, j), l(i, j-1)).
Intuition: when the last characters match, you extend the LCS of the prefixes (remove both last characters and add 1). When they do not match, you try removing the last character from one sequence or from the other and take the best result.
Why some given expressions are incorrect:
The expression 'expr1 ≡ l(i-1, j) + 1' is incorrect because it removes only one of the two matched characters; the correct matched-prefix LCS must remove both, i.e., l(i-1, j-1) + 1.
The expression 'expr1 ≡ l(i, j-1)' is incorrect for the match case because it does not add 1 and does not remove both matched characters.
The expression 'expr2 ≡ max(l(i-1, j), l(i, j-1))' is correct for the mismatch case since it considers dropping the last character from either sequence.
The expression 'expr2 ≡ max(l(i-1, j-1), l(i, j))' is invalid because it is circular (l(i,j) appears on both sides) and l(i-1, j-1) alone does not capture the best of removing a single last character.
Summary: The correct full recursive definition is
l(i,j) = 0, if i = 0 or j = 0;
l(i,j) = l(i-1, j-1) + 1, if X[i-1] = Y[j-1];
l(i,j) = max(l(i-1, j), l(i, j-1)), if X[i-1] ≠ Y[j-1].
A video solution is available for this question — log in and enroll to watch it.