In general, the hardest task of dynamic programming is to find and define the right recursion for the problem a recursion that makes exponentially-many recursive calls in a direct implementation, and yet all of the calls are in some poly-size domain. For each problem below, find such a recursion. Then explain how you solve the problem in a bottom-up fashion by using a suitably defined array and a formula to fill the array based on previously-filled cells. For this problem you do not need to write a pseudocode as part of your explanation.

a. (5 marks) The Longest Sub-Palindrome problem: given a sequence X = find the longest subsequence such that ij < ij+1 for any j, and that is a palindrome: k is even and the inverse sequence is identical to the original sequence . (E.g., abba is a sub-palidrome of tablebrand.)

b. (5 marks) The Longest Simple Path problem: Suppose that we are given a directed acyclic graph G = (V, E) with real-valued weights and two distinguished vertices s and t. The goal is to find a longest weighted simple path from s to t.