In this question, we demonstrate an approach for improving space complexity using the Longest Common Subsequence (LCS) problem. First we will design the standard LCS algorithm, and then we will modify it for a better space complexity. The LCS problem takes two strings of length n as input and returns the LCS of the two strings. Recall that a subsequence of a string s is the concatenation of disjoint substrings of s in the same order as they exist in s. For example, for the string HOMEWORK, HOME is a subsequence (HOME is a substring) and HOOK is a subsequence (HO,O,K are substrings occuring in that order) but HERO is not a subsequence of HOMEWORK because no O exists after any R in HOMEWORK. The LCS of a pair of strings s1, s2 is the longest string s such that s is a subsequence of both s1 and s2. There may be multiple distinct LCSs, but if you are asked to return the LCS then returning any LCS of the proper length is correct. For this problem, you may assume that the strings both have length n, and you can refer to characters of string s1 using s1[i] for i {1, ..., n} and string s2 using s2[j] for j {1, ..., n}. You may be asked to return either the LCS or the length of the LCS in different parts of the question.

a) Describe the set of subproblems that your dynamic programming algorithm will consider if your trying to solve for the LCS of two strings. Your solution should look something like For every ..., we define OPT[...] to be ...

b) Give a recurrence expressing each subproblem OPT[...] in terms of the solution to smaller subproblems.

c) Using your recurrence, design a dynamic programming algorithm which uses at most O(n 2 ) time and space to output the LCS of a pair of strings. Analyze the time and space complexity of your algorithm.

d) Modify your algorithm from part (c) in order to use at most O(n 2 ) time and at most O(n) space if you only return the length of the LCS. Analyze the time and space complexity of your algorithm.

e) Finally, design an O(n 2 ) time and O(n) space algorithm to compute the LCS. Hint: Use divide-and-conquer to find the LCSs for the first and second half of s2 separately.