Suppose you are given a table c that was used to compute an LCS, but not the ori
ID: 3848769 • Letter: S
Question
Suppose you are given a table c that was used to compute an LCS, but not the original strings. Assume that the input string X is represented down the rows and Y across the columns. Remember that the first row and column represented are for empty strings, and that, for example, c[1,1] corresponds to the LCS X1 and Y1.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
0
1
1
2
2
2
2
2
0
1
1
2
2
2
2
2
0
1
1
2
3
3
3
3
0
1
1
2
3
3
3
4
0
1
2
2
3
3
3
4
6A: 5 points
What is the length of the LCS of X and Y ?
6B: 15 points
Since we don’t have the original input strings X and Y, we can’t figure out the letters in their LCS. But given the table above, we can figure out the indices of the LCS in the original string X.
Using the table, list the indices of X that would be part of the LCS solution. Remember that, according to our usual conventions, strings are indexed from 1.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
0
1
1
2
2
2
2
2
0
1
1
2
2
2
2
2
0
1
1
2
3
3
3
3
0
1
1
2
3
3
3
4
0
1
2
2
3
3
3
4
Explanation / Answer
6A) The Longest Common Subsequence of X1 and Y1 is 4. Because The final value of the matrix reffers the Length of the LCS.
6B) Here I am assumeing that X1 indexs are from 0-7 like X1[0],X1[2],X1[3]...X1[7].
--> and to find the instances of X1 we will start from Final element that is c[7,7] which is 4.
--> Will Traceback from final to first to find the Longest Common Subsequence.
---> Now include the instance of X1[7] in subsequence. Here analyse that from where this value 4 has come, In this case it is MAXIMUM of left and upper values of 4 which is 4. so, move upwards.
---> again analyse that from where this value has come, in this case it the sum of its diagonal values + 1 . so, move diagonally left side and include the instance of X1 in that row in Subsequence.
WE INCLUDE X1 INSTANCES ONLY WHEN WE TAKE LEFT DIAGONAL MOVEMENT.
---> Please follow my explanation correclty and repeat it till you reach the starting values and you will get the Instance of X1.
FINALLY I HAVE GOT THESE AS SUBSEQUENCE
X1[1], X1[2], X1[4], X1[5], X1[7].
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.