(20pts) In this question, we study the Largest Palindrome Subsequence problem di

Question

(20pts) In this question, we study the Largest Palindrome Subsequence problem discussed in Quiz6_7 again. The 2nd question of the quiz developed a dynamic programming algorithm that runs in Q(n3) time. Improve the running time into Q(n2). Describe all of: 2. o your basic method explained in 3-10 lines in English, o complete pseudo code, o proof of the algorithm correctness, and o proof of the running time O(r2) Make your answers succinct but include everything necessary to reason the above. Hint: The function isPalindrome is called every time the main algorithm checks if sli to j] is a palindrome. This part refers to no previous computation being inefficient. Can you modify isPalindrome to act as a DP algorithm itself? write answers here PerTU: erfit%yyC?% liE:rE2 " " " " " " " " " " "

Explanation / Answer

First of all Let us understand the problem in a simple way:

f(i, i) = 1 for all indexes i in given sequence

because the subsequence starting and ending at same position. So the longest length=1

if (j == i + 1 &s[i]==s[j]) f(i, j) = 2

because if the indexes i and j are consecutive and s[i] ==s[j]. So longest subsequence will be of length 2

ie. If the letters at indices do not match then the above condition holds true. either we consider the last letter or we dont consider it.

ie. If both letters match then above condition holds true.

Here we see that we are solving the same subproblems again and again.

Here is the pseudocode for the O(n2)Solution

Table to store results of subproblems
palin[n][n];
All strings of length one are palindromes
for (i = 0; i < n; i++)
palin[i][i] = 1;
for (k=2; k<=n; k++)
{
for (i=0; i<n-k+1; i++)
{
j = i+k-1;
if (string[i] == string[j] && k == 2)
L[i][j] = 2;
else if (string[i] == string[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];

Here we see that the there are 2 for loops and the timecomplexity is O(n2).

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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