This problem will walk you through the steps of designing a dynamic program. The problem we...

Transcribed Image Text:

This problem will walk you through the steps of designing a dynamic program. The problem we are solving is the longest palindrome problem: given a string, S, what is the length of the longest palindrome that is a substring of S? A palindrome is a string that reads the same forwards as backwards. For example, "racecar", "eve", and "1", are all palindromes. We also consider the empty string to be a palindrome (of length 0). (a) First we need to figure out what our subproblems are. Since we are working with strings, a natural subproblem to use is substrings. Let OPT(i, n) denote the length of the longest palindrome in the substring of length in starting at index i. Write an expression for the recursive case of OPT(i,n). (Hint: All palindromes above a certain size have palindromes as substrings). (b) Next we need a base case for our OPT recurrence. Write an expression for the base case(s) of this recurrence. (Hint: Which size strings are always palindromes?) (c) Now that we have a complete recurrence, we need to figure out which order to solve the subproblems in. Which subproblems does the recursive case OPT(i, n) require to be calculated before it can be solved? (d) Given these dependencies, what order should we loop over the subproblem in? (e) We have all of the pieces required to put together a dynamic program now. Write psuedocode for the dynamic program that computes the length of the longest palindromic substring of S. This problem will walk you through the steps of designing a dynamic program. The problem we are solving is the longest palindrome problem: given a string, S, what is the length of the longest palindrome that is a substring of S? A palindrome is a string that reads the same forwards as backwards. For example, "racecar", "eve", and "1", are all palindromes. We also consider the empty string to be a palindrome (of length 0). (a) First we need to figure out what our subproblems are. Since we are working with strings, a natural subproblem to use is substrings. Let OPT(i, n) denote the length of the longest palindrome in the substring of length in starting at index i. Write an expression for the recursive case of OPT(i,n). (Hint: All palindromes above a certain size have palindromes as substrings). (b) Next we need a base case for our OPT recurrence. Write an expression for the base case(s) of this recurrence. (Hint: Which size strings are always palindromes?) (c) Now that we have a complete recurrence, we need to figure out which order to solve the subproblems in. Which subproblems does the recursive case OPT(i, n) require to be calculated before it can be solved? (d) Given these dependencies, what order should we loop over the subproblem in? (e) We have all of the pieces required to put together a dynamic program now. Write psuedocode for the dynamic program that computes the length of the longest palindromic substring of S.

Answer rating: 100% (QA)

a The recursive case for OPTi n can be expressed as follows if Si Si n 1 The first and last characters of the substring match OPTi n 2 OPTi 1 n 2 if n ... View the full answer