Question 2 (10 marks) In general, the hardest task of dynamic programming is to

Question

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

Explanation / Answer

Hi, Please find the algorithm for Q1[Longest Palindromic Sequence].

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)).

Following is a general recursive solution with all cases handled.

// Everay single character is a palindrom of length 1
L(i, i) = 1 for all indexes i in given sequence

// IF first and last characters are not same
If (X[i] != X[j]) L(i, j) = max{L(i + 1, j),L(i, j - 1)}

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2

// If there are more than two characters, and first and last
// characters are same
Else L(i, j) = L(i + 1, j - 1) + 2

            L(0, 5)
/
/
L(1,5) L(0,4)
/ /
/ /
L(2,5) L(1,4) L(1,4) L(0,3)

In the above partial recursion tree, L(1, 4) is being solved twice.
If we draw the complete recursion tree, then we can see that there are many subproblems which are solved again and again

// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }

// Returns the length of the longest palindromic subsequence in seq
int longestPalindromicSequence(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. The values are filled in a
// manner similar to Matrix Chain Multiplication DP solution
//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];
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.