1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset...

Transcribed Image Text:

1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset of not-necessarily- consecutive characters (X[i], X[i₂].....X[ik]) such that i₁ <i₂ <... <ik. A subsequence can be empty (i.e., k = 0). A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Note that a palindrome may have an odd number of characters. (a) Let MaxPalSub(i, j) be the length of the longest subsequence of X[i.. j] that is also a palindrome. (For simplicity, we treat X[i .. j] as empty if i>j.) Fill in the blanks to complete the following recursive definition of Max PalSub(i, j). MaxPalSub(i, j)=2+ MaxPalSub(i+1,. (MaxPalSub(i,- MaxPalSub( max if i > j if i = j if i <j and X[i]=x[j] otherwise Advice: Suppose j>i. The longest palindrome in X[i.. j] should start with X[i] and end with X[j] if X[i]=X[j]. Otherwise, it must exclude at least one of X[i] or X[j]. (b) Use dynamic programming to write a method in Java that takes as its one parameter an array x of characters and returns the length of the longest palindrome subsequence in x. Your method should be based on the above recurrence and run in O(n²) time given an array of length n. (You can handwrite or type your code. Either way, it won't actually be compiled.) 1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset of not-necessarily- consecutive characters (X[i], X[i₂].....X[ik]) such that i₁ <i₂ <... <ik. A subsequence can be empty (i.e., k = 0). A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Note that a palindrome may have an odd number of characters. (a) Let MaxPalSub(i, j) be the length of the longest subsequence of X[i.. j] that is also a palindrome. (For simplicity, we treat X[i .. j] as empty if i>j.) Fill in the blanks to complete the following recursive definition of Max PalSub(i, j). MaxPalSub(i, j)=2+ MaxPalSub(i+1,. (MaxPalSub(i,- MaxPalSub( max if i > j if i = j if i <j and X[i]=x[j] otherwise Advice: Suppose j>i. The longest palindrome in X[i.. j] should start with X[i] and end with X[j] if X[i]=X[j]. Otherwise, it must exclude at least one of X[i] or X[j]. (b) Use dynamic programming to write a method in Java that takes as its one parameter an array x of characters and returns the length of the longest palindrome subsequence in x. Your method should be based on the above recurrence and run in O(n²) time given an array of length n. (You can handwrite or type your code. Either way, it won't actually be compiled.) 1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset of not-necessarily- consecutive characters (X[i], X[i₂].....X[ik]) such that i₁ <i₂ <... <ik. A subsequence can be empty (i.e., k = 0). A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Note that a palindrome may have an odd number of characters. (a) Let MaxPalSub(i, j) be the length of the longest subsequence of X[i.. j] that is also a palindrome. (For simplicity, we treat X[i .. j] as empty if i>j.) Fill in the blanks to complete the following recursive definition of Max PalSub(i, j). MaxPalSub(i, j)=2+ MaxPalSub(i+1,. (MaxPalSub(i,- MaxPalSub( max if i > j if i = j if i <j and X[i]=x[j] otherwise Advice: Suppose j>i. The longest palindrome in X[i.. j] should start with X[i] and end with X[j] if X[i]=X[j]. Otherwise, it must exclude at least one of X[i] or X[j]. (b) Use dynamic programming to write a method in Java that takes as its one parameter an array x of characters and returns the length of the longest palindrome subsequence in x. Your method should be based on the above recurrence and run in O(n²) time given an array of length n. (You can handwrite or type your code. Either way, it won't actually be compiled.) 1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset of not-necessarily- consecutive characters (X[i], X[i₂].....X[ik]) such that i₁ <i₂ <... <ik. A subsequence can be empty (i.e., k = 0). A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Note that a palindrome may have an odd number of characters. (a) Let MaxPalSub(i, j) be the length of the longest subsequence of X[i.. j] that is also a palindrome. (For simplicity, we treat X[i .. j] as empty if i>j.) Fill in the blanks to complete the following recursive definition of Max PalSub(i, j). MaxPalSub(i, j)=2+ MaxPalSub(i+1,. (MaxPalSub(i,- MaxPalSub( max if i > j if i = j if i <j and X[i]=x[j] otherwise Advice: Suppose j>i. The longest palindrome in X[i.. j] should start with X[i] and end with X[j] if X[i]=X[j]. Otherwise, it must exclude at least one of X[i] or X[j]. (b) Use dynamic programming to write a method in Java that takes as its one parameter an array x of characters and returns the length of the longest palindrome subsequence in x. Your method should be based on the above recurrence and run in O(n²) time given an array of length n. (You can handwrite or type your code. Either way, it won't actually be compiled.) 1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset of not-necessarily- consecutive characters (X[i], X[i₂].....X[ik]) such that i₁ <i₂ <... <ik. A subsequence can be empty (i.e., k = 0). A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Note that a palindrome may have an odd number of characters. (a) Let MaxPalSub(i, j) be the length of the longest subsequence of X[i.. j] that is also a palindrome. (For simplicity, we treat X[i .. j] as empty if i>j.) Fill in the blanks to complete the following recursive definition of Max PalSub(i, j). MaxPalSub(i, j)=2+ MaxPalSub(i+1,. (MaxPalSub(i,- MaxPalSub( max if i > j if i = j if i <j and X[i]=x[j] otherwise Advice: Suppose j>i. The longest palindrome in X[i.. j] should start with X[i] and end with X[j] if X[i]=X[j]. Otherwise, it must exclude at least one of X[i] or X[j]. (b) Use dynamic programming to write a method in Java that takes as its one parameter an array x of characters and returns the length of the longest palindrome subsequence in x. Your method should be based on the above recurrence and run in O(n²) time given an array of length n. (You can handwrite or type your code. Either way, it won't actually be compiled.) 1. Let X[0.. n-1] be an array of characters. A subsequence of X is a subset of not-necessarily- consecutive characters (X[i], X[i₂].....X[ik]) such that i₁ <i₂ <... <ik. A subsequence can be empty (i.e., k = 0). A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Note that a palindrome may have an odd number of characters. (a) Let MaxPalSub(i, j) be the length of the longest subsequence of X[i.. j] that is also a palindrome. (For simplicity, we treat X[i .. j] as empty if i>j.) Fill in the blanks to complete the following recursive definition of Max PalSub(i, j). MaxPalSub(i, j)=2+ MaxPalSub(i+1,. (MaxPalSub(i,- MaxPalSub( max if i > j if i = j if i <j and X[i]=x[j] otherwise Advice: Suppose j>i. The longest palindrome in X[i.. j] should start with X[i] and end with X[j] if X[i]=X[j]. Otherwise, it must exclude at least one of X[i] or X[j]. (b) Use dynamic programming to write a method in Java that takes as its one parameter an array x of characters and returns the length of the longest palindrome subsequence in x. Your method should be based on the above recurrence and run in O(n²) time given an array of length n. (You can handwrite or type your code. Either way, it won't actually be compiled.)

Answer rating: 100% (QA)

a MaxPalSubi j if i j 0 else if i j 1 else if Xi Xj 2 MaxPalSubi 1 j 1 else ... View the full answer