Reference no: EM133940313

Question

A subsequence of a sequence is anything obtained from a sequence by extracting a subset of elements, but keeping them in the same order; the elements of the subsequence need not be contiguous in the original sequence. For example, the strings C, DAMN, YAIOAI, and DYNAMICPROGRAMMING are all subsequences of the string DYNAMICPROGRAMMING.

1. Let A[1..m] and B[1..n] be two arbitrary arrays. A common subsequence of A and B is another sequence that is a subsequence of both A and B. A longest common subsequence 2 of A and B is a subsequence of A and B of maximum length. For example, if A = (CT GCGT GT C) and B = (GT CGT GGC), then the length of the longest common subsequence of A and B is 6, and the sequence (T CGT GC)is such a longest common subsequence of A and B. Describe an O(nm)-time algorithm to compute the length of the longest common subsequence of two given sequences A and B. (Hint. You may modify the Edit Distance algorithm so that you consider only the two operations: Insert and Delete. What is the connection between this variant of Edit Distance and the problem of computing a longest common subsequence?)

2. A palindrome is any sequence that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Use part (a) above to give an O(n^2 )-time algorithm to find the length of the longest subsequence of a given sequence of length n that is also a palindrome.