Please do in pseudocode.

Let X [1 . . . m] and Y [1 . . . n] be two given arrays. A common supersequence of X and Y is an array Z[1 such that X and Y are both subsequences of Z[l...k]. Your goal is to find the shortest common super- sequence (SCS) Z of X and Y, solving the following sub-problems. a) First, concentrate on finding only the length k of Z. Proceeding similarly to the longest common subsequence problem, define the appropriate array Mo. ..m,0 n] (in English), and write the key recurrence equation to recursively compute the values M[i,j] depending on some relation between Xi and Y]. Do not forget to explicitly write the base cases M[0.j and Mi,0], where b) Translate this recurrence equation into an explicit bottom-up O(mn) time algorithm that computes the length of the shortest common supersequence of X and Y e) Find the SCS of X = NONE and Y-NOON, and give the result of a full run of the algorithm from part (b), including the array M and arrows pointing to where the optimal solution should go. (Notice, you need to find the actual SCS, not only its length.) d) Show that the length k of the array Z computed in part (a) satisfies the equation k m+n-l, whereis the length of the longest common subsequence of X and Y Hint: Use the recurrence equation in part (a), 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+b Let X [1 . . . m] and Y [1 . . . n] be two given arrays. A common supersequence of X and Y is an array Z[1 such that X and Y are both subsequences of Z[l...k]. Your goal is to find the shortest common super- sequence (SCS) Z of X and Y, solving the following sub-problems. a) First, concentrate on finding only the length k of Z. Proceeding similarly to the longest common subsequence problem, define the appropriate array Mo. ..m,0 n] (in English), and write the key recurrence equation to recursively compute the values M[i,j] depending on some relation between Xi and Y]. Do not forget to explicitly write the base cases M[0.j and Mi,0], where b) Translate this recurrence equation into an explicit bottom-up O(mn) time algorithm that computes the length of the shortest common supersequence of X and Y e) Find the SCS of X = NONE and Y-NOON, and give the result of a full run of the algorithm from part (b), including the array M and arrows pointing to where the optimal solution should go. (Notice, you need to find the actual SCS, not only its length.) d) Show that the length k of the array Z computed in part (a) satisfies the equation k m+n-l, whereis the length of the longest common subsequence of X and Y Hint: Use the recurrence equation in part (a), 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+b