Now let’s build a different grid: one for the Dynamic Programming solution for L
ID: 3848767 • Letter: N
Question
Now let’s build a different grid: one for the Dynamic Programming solution for LCS. Recall that the table c in our solution is defined as follows:
c[i,j] = 0 if i = 0 or j = 0
c[i,j] = c[i-1, j-1]+1 if i,j > 0 and xi = yi
c[i,j] = max(c[i,j-1], c[i-1, j]) if i,j > 0 and xi yi
Suppose the inputs to this problem are X = alsdfkj and Y = dfjsk.
A: Start with some clarifying definitions. What are:
X0
X1
X5
Y2
Y5
B: What is contained in row 1 after the first complete j iteration of the LCS DP-based solution? That is, assume i = 1, and j has iterated from 1 to n fully. (See CLRS p. 394 for the pseudocode, and remember to be careful about the size of the row.)
C: What is contained in row 5 after the first complete j iteration of the LCS DP-based solution? That is, assume i is 5, and j has iterated from 1 to n fully for i = 1, 2, 3, 4, and 5.
D: In what cell of the table c is the final answer to the LCS question contained? What number is stored there after the algorithm has run to completion?
Explanation / Answer
X= alsdfkj Y = dfjsk
A) X0 = empty
X1 = a
X5 = f
Y2 = f
Y5 = k
B)
The row 1 contains all zeros since ,
x1 = a is not equals to any yj for any j =1,2,3,4,5
and C[0,j] =0 for all j=1,2,3,4,5
For answering the remaining question lets fill the table using the above given recurrences
The table will be
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
2
2
1
2
2
2
3
1
2
3
3
3
C) So the frow 5 contains 1 2 2 2 2
D) The cell c[7,5] contains the final answer to LCS question and the number stored after completion of algorithm is 3
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
2
2
1
2
2
2
3
1
2
3
3
3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.