Computer Science 3650
Spring 2012
Practice Questions for Quiz 5

1. A palindrome is a string that is equal to its own reversal. For example, civic is a palindrome. A subsequence of a sequence is obtained by deleting zero or more of the sequence's members, preserving order. You would like an algorithm that takes a string and yields the longest subsequence of that string that is a palindrome. For example, if the inpute string is character, then the result is carac. But instead of looking at the full problem, let's focus on just finding the length of the longest subsequence that is a palindrome. So, on input character, the result is 5.

   1. For a given string s = s₁...s_n, let P(i, j) be the length of the longest subsequence of s_i...s_j that is a palindrome. Write recurrences for P(i, j).

   2. Write an efficient algorithm to compute P(1, n) for a given string s = s₁...s_n.

   3. How much time does your algorithm use, to within a constant factor?

2. Consider the following algorithm for finding the longest subsequence of a string that is a palindrome.

     PalSubseq(s1...sn)
       If n == 0
         return s;
       else if n == 1
         return s;
       else
         j = the largest index (from 2 to n) such that sj = s1;
         if j == 1
           return s1;  // a string of length 1
         else
           q = PalSubseq(s2...sj-1);
           return s1 + q + sj;   // + is concatenation
   

   That algorithm only takes O(n) time. Does it work? If so, explain why. If not, give a counterexample (an input on which it gives the wrong answer).