Consider two sequences X and Y: X = <0, 1, 2, 1, 3, 0, 1> y = <1, 3, 2, 0, 1,…
2018
Consider two sequences X and Y:
X = <0, 1, 2, 1, 3, 0, 1>
y = <1, 3, 2, 0, 1, 0>
The length of longest common subsequence between X and Y is
- A.
2
- B.
3
- C.
4
- D.
5
Attempted by 272 students.
Show answer & explanation
Correct answer: C
Final result: The length of the longest common subsequence is 4.
One common subsequence of length 4 is 1, 2, 0, 1.
Method: Use dynamic programming. Let C[i][j] be the LCS length for the prefixes X[1..i] and Y[1..j].
Recurrence: if X[i] = Y[j], then C[i][j] = C[i-1][j-1] + 1; otherwise C[i][j] = max(C[i-1][j], C[i][j-1]).
Filling the table for X = <0,1,2,1,3,0,1> and Y = <1,3,2,0,1,0> yields the final value C[7][6] = 4.
Example alignment (positions):
Subsequence values: 1, 2, 0, 1
Positions in X: 2, 3, 6, 7
Positions in Y: 1, 3, 4, 5
A video solution is available for this question — log in and enroll to watch it.