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 f

rom index i to j s[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.)