3. Consider the following problem and answer questions a) to c). A subsequence is a palindrome if it is the same when re

[answerhappygod]

3 Consider The Following Problem And Answer Questions A To C A Subsequence Is A Palindrome If It Is The Same When Re 1 (54.55 KiB) Viewed 23 times

3. Consider the following problem and answer questions a) to c). A subsequence is a palindrome if it is the same when read left to right and right to left. A subsequence does not have to be contiguous. Describe an efficient algorithm to find the longest subsequence which is a palindrome in a given string A = a₁a2... an. For example, the string abcab contains four palindromes of length 3 as subsequence: aba, aca, bcb, and bab, but no palindrome of length 4; thus, any palindrome of length 3 is an optimal solution. a) Create a recursive function L(i, j) that represents the length of the longest subsequence which is a palindrome in a, ... Aaj. b) How to create a memo to record the value of each L(i, j)? And to actually find the longest subsequence which is a palindrome in A, what extra info is needed? c) How to use the memo to find the solution to the problem? What is the running time of this dynamic programming algorithm?