In: Computer Science
Problem 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).
a) (4 points) Describe the optimal substructure of the MPSP and give a recurrence equation for L(i,j).
b) (6 points) Describe an algorithm that uses dynamic programming to solve the MPSP. The running time of your algorithm should be O(n2).
a) Optimal substructure of MPSP: A given problem is said to have optimal substructure property if an optimal solution of the given problem can be obtained by using optimal solutions of its subproblems
Therefore, in this case to find MPSP in a string, we find the MPSP in substrings of this string.
To understand this quickly let's take a short example: "A B G B B D A" (lets take 1 based index)
for MPSP in string [ 1, 7 ] --> check if (string[1] == string[7]) and find MPSP in substring [ 2, 6]
Therefore,
if last and first character of string are same --> MPSP = 2 + MPSP of substring(first + 1 , last - 1 ) [ 2 because if first and last index are same then there is palindromic subsequence of al least length = 2 ]
else ----> MPSP = max(MSP of substring(first + 1, last), MPSP ofsubstr( first, last - 1))
Recurrence solution: We use bottom-up approach to solve this problem i.e we'll first calculate MPSP for substrings of smaller length and then move towards MPSP of substrings with greater length.
we maintain a dp table, in which index i, j shows the MPSP in substring( i, j )
therefore, for every i == j we get substrings of length 1, and substring of length 1 is a palindromic subsequence of 1 so we'll mark all diagonal element with 1.
for every substring of length 2 if they are palindromic then, the MPSP for that substring would be of length 2.
therefore, recursive solution:
if (inputString[ i ] == inputString[ j ] and j == i + 1): <-------- for palindromic substring of length 2
then, dpTable[ i ] [ j ] = 2
else if (inputString[ i ] == inputString[ j ] ):
then, dpTable[ i ] [ j ] = 2 + dpTable[ i + 1 ] [ j - 1]
else:
then, dpTable[ i ] [ j ] = maximum(dpTable [ i + 1] [ j ], dpTable[ i ] [ j - 1] )
b) Maintain a dp table, in which the index i,j denote MPSP in substring( i, j ):
Every substring i == j, is a palindromic substring of length 1
~ | A | B | G | B | B | D | A |
A | 1 | ||||||
B | 1 | ||||||
G | 1 | ||||||
B | 1 | ||||||
B | 1 | ||||||
D | 1 | ||||||
A | 1 |
for length 2: AB, BG, GB, BB,BD, DA
for i=0, j=1, i.e AB, first and last are not same, i.e A is not same as B,
therefore, dpTable[ 0 ][ 1 ] = max(dpTable[ 1 ] [1] , dpTable[0] [ 0]) = max(1, 1) = 1
and for i=3, j=4, i.e BB, first and last are same,
therefore, dpTable[3][4] = 2 + dpTable[4][3] = 2
similarly for every other substring of length 2, maximum substring is of length 1, therfore;
~ | A | B | G | B | B | D | A |
A | 1 | 1 | |||||
B | 1 | 1 | |||||
G | 1 | 1 | |||||
B | 1 | 2 | |||||
B | 1 | 1 | |||||
D | 1 | 1 | |||||
A | 1 |
For length 3: ABG, BGB, GBB, BBD, BDA
for ABG: i.e i = 0 and j = 2
since string[0] is not same as string[2], therefore, dpTable[0][2] = max( 1, 1) = 1
for BGB, i.e i = 1 and j = 3
since string[1] == string[3] , therefoer, dpTable[1][3] = 2 + dpTable[2][2] = 2+1 = 3
for GBB, i.e i = 2 and j = 5
string[2] is not same as string[5], therefore, dpTable[2][5] = max(dpTable[3][5], dpTable[2, 4]) = max(2, 1) = 2
therefore, after computing for all length 3 we get:
~ | A | B | G | B | B | D | A |
A | 1 | 1 | 1 | ||||
B | 1 | 1 | 3 | ||||
G | 1 | 1 | 2 | ||||
B | 1 | 2 | 2 | ||||
B | 1 | 1 | 1 | ||||
D | 1 | 1 | |||||
A | 1 |
Therefore, after performing above recursive for all the remaining length:
we get:
~ | A | B | G | B | B | D | A |
A | 1 | 1 | 1 | 3 | 3 | 3 | 5 |
B | 1 | 1 | 3 | 3 | 3 | 3 | |
G | 1 | 1 | 2 | 2 | 2 | ||
B | 1 | 2 | 2 | 2 | |||
B | 1 | 1 | 1 | ||||
D | 1 | 1 | |||||
A | 1 |
Algorithm:
n = length(string)
// strings of length 1 are palindrome of length 1
for i in range(n-1):
dpTable[i][i] = 1
// Lower diagonal values are of no use to us
// therefore, we are just not filling in them in the process.
// iterating every subdiagonals from 0 to last index
for subDiagonal in range(2, n+1):
// iterating every row from index j+1 to last index.
for row in range(0, n-subDiagonal+1):
// compute the current column value.
column = row + subDiagonal - 1
// APPLY RECURSIVE EQUATION:
if string[row] == string[column] and column == row+1:
dpTable[row][column] = 2
else if string[row] == string[column]:
dpTable[row][column] = 2 + dpTable[row+1][column-1]
else:
dpTable[row][column] = max(dpTable[row+1][column], dpTable[row][column-1])
return dpTable[0][n-1]