Question

In: Computer Science

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

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

Solutions

Expert Solution

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]

Related Solutions

5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, ....
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, . . . , n] of positive integers, an integer K. Decide: Are there integers in A such that their sum is K. (Return T RUE or F ALSE) Example: The answer is TRUE for the array A = [1, 2, 3] and 5, since 2 + 3 = 5. The answer is FALSE for A = [2, 3, 4] and 8. Note that you...
The purpose of this C++ programming assignment is to practice using an array. This problem is...
The purpose of this C++ programming assignment is to practice using an array. This problem is selected from the online contest problem archive, which is used mostly by college students worldwide to challenge their programming ability and to prepare themselves for attending programming contests such as the prestige ACM International Collegiate Programming Contest. For your convenience, I copied the description of the problem below with my note on the I/O and a sample executable. Background The world-known gangster Vito Deadstone...
Objective: The purpose of this programming assignment is to practice using STL containers. This problem is...
Objective: The purpose of this programming assignment is to practice using STL containers. This problem is selected from the online contest problem archive (Links to an external site.), which is used mostly by college students world wide to challenge their programming ability and to prepare themselves for attending programming contests such as the prestige ACM International Collegiate Programming Contest (Links to an external site.). For your convenience, I copied the description of the problem below with my note on the...
1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms,...
1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms, implement an algorithm. In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An algorithm for making change using the smallest possible number of coins repeatedly returns the biggest coin smaller than the amount to be changed until it is zero. For example, 17 cents will result in the series 10 cents, 5 cents, 1 cent, and 1...
Dynamic Programming Question. Make the table for finding a LCS (Longest Common Subsequence) of the strings...
Dynamic Programming Question. Make the table for finding a LCS (Longest Common Subsequence) of the strings SLWOVNNDK and ALWGQVNBKB. You need to Show the traceback for the LCS.
Build a Dynamic Programming algorithm in Python for the following problem. Given two sequences of vowels,...
Build a Dynamic Programming algorithm in Python for the following problem. Given two sequences of vowels, find the length of longest subsequence present in both of them. NOTE: A subsequence is a sequence that appears in the same order, but not necessarily contiguous. For example, “aei”, “aeo”, “eio”, “aiu”, ... are subsequences of “aeiou”. Sample Input 1: aeiou aiu Sample Output 1: 3 Sample Input 2: aeaiueoiuaeeoeooaauoi aeuioauuuoaeieeaueuiouaiieuiuuuaoueueauaeiauuo Sample Output 2: 16 Sample Input 3: iioioieiaiauaoeoiioiiue iuuueauiaieooaoaaouaaaae Sample Output 3:...
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for...
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for n objects with a knapsack capacity of K. In particular, we characterized our recurrence OPT(j, W) to be following quantity: OPT(j, W) := The maximum profit that can be obtained when selecting from objects 1, 2, . . . , j with a knapsack capacity of W , where (after filling in our dynamic programming table), we return the value stored at OPT(n, K)...
Using the dynamic programming-based algorithm for chain matrix multiplcation, show the best way to multiply a...
Using the dynamic programming-based algorithm for chain matrix multiplcation, show the best way to multiply a chain of matrices with dimensions that are: 10x5, 5x2, 2x20, 20x12, 12x4 and 4x60. Finally, use the resulting tables to provide the complete optimal parenthesization of the matrix chain product A0 · A1 · A2 · A3 · A4 · A5.
C programming problem I have to design an efficient algorithm which solves this problem. Also, it...
C programming problem I have to design an efficient algorithm which solves this problem. Also, it needs to include time and space complexities of this algorithm. There is a matrix (N times N) of integers which rows and columns are sorted in non-decreasing order. A sorted matrix and integer M will be given and we need to find the position(row,column) of M in this matrix. it's okay to report only one position if there are more than one answers. when...
Program in Java using Inheritence The purpose of this assignment is to practice OOP programming covering...
Program in Java using Inheritence The purpose of this assignment is to practice OOP programming covering Inheritance. Core Level Requirements (up to 6 marks) The scenario for this assignment is to design an online shopping system for a local supermarket (e.g., Europa Foods Supermarket or Wang Long Oriental Supermarket). The assignment is mostly concentrated on the product registration system. Design and draw a UML diagram, and write the code for the following classes: The first product category is a fresh...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT