Answered You can hire a professional tutor to get the answer.
LetX[1. m] andY[1. n] be two given arrays. A common supersequence ofXandYis an arrayZ[1. k] such thatXandYare both subsequences ofZ[1.
Let X[1 . . . m] and Y [1 . . . n] be two given arrays. A common supersequence of X and Y is an arrayZ[1 . . . k] such that X and Y are both subsequences of Z[1 . . . k]. Your goal is to find the shortestcommon super-sequence (SCS) Z of X and Y , solving the following sub-problems.
Show that the length k of the array Z computed in part (a) satisfies the equation k=m+n−l ,
where l is the length of the longest common subsequence of X andY. (Hint: Use the recurrence equation of computing SCS, then combine it with a similar recurrence equation for the LCS, and then use induction. There the following identity is very handy: min(a, b) + max(a, b) = a + b.)
