A 2. Purpose: practice algorithm design using dynamic programming. A subsequence is palindromic if it is...

Transcribed Image Text:

A 2. Purpose: practice algorithm design using dynamic programming. A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence A,C,G,T,G,T,C,A,A,A,A,T,C,G has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Assume you are given a sequence x[1.n] of characters. Denote L(i,j) the length of the longest palindrome in the substring x[i,.j]. The goal of the Maximum Palindromic Subsequence Problem (MPSP) is to take a sequence x[1,.,n] and return the length of the longest palindromic subsequence L(1,n). Describe the optimal substructure of the MPSP and give a recurrence equation for L(i,j). Describe an algorithm that uses dynamic programming to solve the MPSP. The running time of your algorithm should be 0(n2). A 2. Purpose: practice algorithm design using dynamic programming. A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence A,C,G,T,G,T,C,A,A,A,A,T,C,G has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Assume you are given a sequence x[1.n] of characters. Denote L(i,j) the length of the longest palindrome in the substring x[i,.j]. The goal of the Maximum Palindromic Subsequence Problem (MPSP) is to take a sequence x[1,.,n] and return the length of the longest palindromic subsequence L(1,n). Describe the optimal substructure of the MPSP and give a recurrence equation for L(i,j). Describe an algorithm that uses dynamic programming to solve the MPSP. The running time of your algorithm should be 0(n2).