Define the longest common subsequence problem: - The input is two sequences seq1
ID: 3830021 • Letter: D
Question
Define the longest common subsequence problem:
- The input is two sequences seq1 = [x0, x1, ..., xn] and seq2 = [y0, y1, ..., yn];
- The output is the length of the longest common subsequence.
This is similar to the edit distance problem, except that we are only allowed insertions and deletions, and no substitution.
a. Express the problem in terms of subproblems and include the base case. (An example of how to do this is given in the notes for the recursive solution for the all-pairs shortest paths problem. The solution is also very similar to the edit distance problem. Try to write down some examples as a place to start).
(b) In preparation for a dynamic programming solution, describe:
the number of dimensions needed by a table which will be used to record the solutions to the subproblems
for each dimension of the table, what the index represents, and what its range of values is
(c) In Java, give a dynamic programming solution to the problem (include the solution as a java file).
(d) What is the time complexity and space complexity of this solution? Justify your answer.
Explanation / Answer
a. Express the problem in terms of subproblems and include the base case. (An example of how to do this is given in the notes for the recursive solution for the all-pairs shortest paths problem. The solution is also very similar to the edit distance problem. Try to write down some examples as a place to start).
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).
If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
(b) In preparation for a dynamic programming solution, describe:
the number of dimensions needed by a table which will be used to record the solutions to the subproblems
for each dimension of the table, what the index represents, and what its range of values is
Dimension will be m+!, n+1
Where L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
(c) In Java, give a dynamic programming solution to the problem (include the solution as a java file).
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b)? a : b;
}
int lcs( String X, String Y, int m, int n )
{
int L[][] = new int [m+1][n+1];
int i, j;
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X.charAt(i-1) == Y.charAt(j-1))
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
(d) What is the time complexity and space complexity of this solution? Justify your answer.
Time Complexity of the above implementation is O(mn) as it scan each charcter of second string for first string
Space complety is also O(mn) in saving solution of sub problem.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.