In this exercise, we consider the problem of finding the largest palindrome subsequence. A string of characters is said to be a palindrome if the reversal is equal to itself. For eg., racecar, civic, a are all palindromes. We are to construct an algorithm to solve the following problem: Input: A non-empty string s Output: A palindrome included in s of the maximum length Fill in the 13 blanks below to complete the description regarding the algorithm. (Total 20 pts. (a),(b),(c),(d),(k),(m): each 1 point. The others: each 2 points) - The indices of a string s of length n are from 1 to n, i.e., s = s[1 to n] = (s[1], s[2], , s[n])

- Allowed keystrokes:

substring of s from index i to js[i to j]

length of s|s|

x to the power j x^j

First, let us write a function isPalindrome(s: string) that returns True if s is a palindrome, and False otherwise. IsPalindrome(s: string) for i-1 to In/2] if s[i] --(a) (b) return return (c) Using the function, our algorithm for the problem is maxPalindrome(s: string) n-61 # B(i, k) will include the largest palindrome included in s[i to i+k] for i-1 ton B(i,0)= for k-1 to n-1 for i-1 to n-k if is True B(i,k) = else if (g) # (h) must be an expression including "+": Enter Carefully B(i,k)= else B(i, k)= return This algorithm runs in o( ) time, and the algorithm paradigm it belongs to is (Here (I) is a function of n, and (m) is either divide and conquer, dynamic programming or greedy algorithm.)