Let us run LCS-LENGTH (X, Y) on the sequences X= and Y=. Select all the statemen
ID: 3807927 • Letter: L
Question
Let us run LCS-LENGTH (X, Y) on the sequences X= and Y=. Select all the statements below which are TRUE: The value of c[4, 3] is the length of an LCS of X and Y. The value of c[4, 3] is 3. The value of c[4.3] is the length of an LCS of X_4 and Y_3. For any i, j such that 1 lessthanorequalto i lessthanorequalto m and 1 lessthanorequalto j lessthanorequalto n. c[m, n] greaterthanorequalto c[i, j]. The value of c[4, 3] is 2. The value of c[4, 3] represents the number of characters that X_4 and Y_3 have in common. b[4, 3] = uparrow b[4, 3] =Explanation / Answer
LCS of two strings X and Y can be found using dynamic programming as
For given strings the table would look like
A
B
D
C
B
0
0
0
0
0
0
C
0
0
0
0
1
1
A
0
1
1
1
1
1
B
0
1
2
2
2
2
C
0
1
2
2 C(4,3)
3
3
D
0
1
2
3
3
4
A
0
1
2
3
3
4
B
0
1
2
3
3
4
Dear friend,
THis is very good example of dynamic programming . Hope this ans helps you to understand it.
A
B
D
C
B
0
0
0
0
0
0
C
0
0
0
0
1
1
A
0
1
1
1
1
1
B
0
1
2
2
2
2
C
0
1
2
2 C(4,3)
3
3
D
0
1
2
3
3
4
A
0
1
2
3
3
4
B
0
1
2
3
3
4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.