Question

The following table is partially filled. 0 1 4 0 Xi 4 D a) Explain why c[1,1] to c[1,5] and c[2,1] to c[5,1] are all 1s? b) Compute c[2,2], and which cell do you refer to when computing it? c) Compute c 2,31 and c[3,2], which cell do you refer to directly this time? d) Fill up the rest of the cells. Assume that you take c[i,j - 1] when there is a draw in line 11. (i.e., take the first element.) Question 2 (2.5 points) Longest common subsequence Consider the procedure to determine the length of the longest common subsequence, LCS- LENGTH(X, Y). It solves the LCS problem in a bottom-up manner, by filling out a 2-D tabular. LCS-LENGTH(X, Y) m-X. length n = Y.length 3. let c[O..m, 0..n] be a new array 4. for i-0 to m 5. for j 0 to n cli,j] = 0 c[i,j]-c[i-i,j-1] + 1 cli, j]-max(c[i, j-1 ], c[i-1, j]) 7. 8. 9. 10. else if X[i]Yl else 12. return c[m, n] For example, X - (B, C, B, D, C) and Y - (B, C, A, B, C), because the last two elements are the same (C), we have LCS(X,Y) LCS(X1:4,h4) + 1. If we represent LCS(X,Y) with the table entry c[5,5], then c[5,5]-c[4,4] +1. Here, c[4,4] is the solution to the subproblem: LCS of (B,C,B,D) and (B,C,A,B). The following table is partially filled.

Answer 1

20 cend both a komf

element 一ーーキャem.. -Lar( onel eoe C) ond bork-ro Aem anar ome aapel aliaanal

1. because in starting we got the match B = B and we add 1 from the previous diagonal element. and by conditions we are taking max of the previous elements.

2. a[2,2] is 2. its come from the diagonal element a[1,1} and add 1 to it. so we get the answer 2

3.a[2,3] = 2 come from the previous a[2,2] because it is maximum one while comparing.

and a[3,2] = 2 come from the previous a[2,2] because it is maximum one while comparing.

both condition i mentioned in the given image.

4.

20 cend both a komf