3 Dynamic Programming Algorithm Lcs Follow Code Determine Lcs Longest Common Subsequence 1 Q37082517

3. Dynamic Programming algorithm for LCS.

(a) Follow the code below to determine an LCS (Longest CommonSubsequence) of < 1, 0, 0, 1, 0, 1, 0, 1 > and < 0, 1, 0,1, 1, 0, 1, 1, 0 >. Please show the 2-D table c and b (as copiedbelow from the textbook Introduction to Algorithms, by T. Cormen,C.E. Leiserson, R. L. Rivest) as being used in the pseudocdeLCS-Length. Note the 2-D tbale b is set so that b[i, j] points tothe table entry corresponding to the optimal subproblem solutionchosen when computing c[i, j].

LCS-Length(X,Y)

m = X.length

n = Y.length

let b[1..m,1..n] and c[0..m,0..n] be

OR

 

OR