In general, the hardest task of dynamic programming is to find and define the “r
ID: 3805136 • Letter: I
Question
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 = <x1, ..., xn> find the longest subsequence <xi1 , ..., xik> such that ij < ij+1 for any j, and that is a palindrome: k is even and the inverse sequence <xik , xik1 , ..., xi1> is identical to the original sequence <xi1 , ..., xik>. (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.
Explanation / Answer
a)
Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0..n-1].
If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).
So this gives us following recursive solution
Solution of this using dynamic programming is to have a table to store result of previous computation of smaller size problem. Here is a solution in c
// Returns the length of the longest palindromic subsequence in seq
int lps(char *str)
{
int n = strlen(str);
int i, j, cl;
int L[n][n]; // Create a table to store results of subproblems
// Strings of length 1 are palindrome of lentgh 1
for (i = 0; i < n; i++)
L[i][i] = 1;
// Build the table. Note that the lower diagonal values of table are
// useless and not filled in the process. cl is length of
// substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}