Question

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 2. n-Y.length 3. let cO.m, 0n] be a new array 4, for i = 0 to m for/ = 0 to n else if ATY ci,ci ,j-1 +1 10 else 12. return clm, 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,Y1:4) + 1. If we represent LCS(X,Y) with the table entry c[5,5], then c[5,5-c[4A] + 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. 3 4 5 ВСАВ a) Explain why c[1,1] to c[1,5] and c[2,1] to c[5,1] are all Is? b) Compute c[2,2], and which cell do you refer to when computing it? c) Compute c[2,3] 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[1,J-1] when there is a draw in line 11. (L.e., take the first element.)

Answer 1

3 5 2 2 2 23 3