Please provide a proof of correctness as well. A common supersequence of two sequences/arrays A[1 .. m] and B[1 .. n] is another sequence that includes both the elements of A and the elements of B in order. For example, if the two sequences are BIOLOGICAL and DIPLOMATICALLY, a common supersequence of those two sequences is DBIOPLOMATG- ICALLY.

For all integers i, j such that 0 i m and 0 j n, let SCS(i, j) denote the length of the shortest common supersequence of sequences A[1 .. i] and B[1 .. j].

(a) Give a recurrence definition or describe a simple recursive algorithm for computing SCS(i, j). You do not need to analyze the algorithm if you choose to describe one. Dont forget to explain why your solution is correct.

(b) Use your solution from part (a) to describe and analyze an O(n2) time dynamic programming algorithm to compute the length of the shortest common supersequence of A[1 .. m] and B[1 .. n].