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.

Question 2 (10 marks) 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 (zi, ...,an) find the longest subsequence 21 ...,zik) such that ij i for any j, and that is a palindrome: k is even and (z j+1 the inverse sequence (z rk-1 i is identical to the original sequence 21 in). (E.g abba is a Ti 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