Computer Science 3650
Spring 2012
Solutions to 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).

      1. P(i, j) = 0 when i > j, since then there are no characters in the index range from i up to j.

      2. P(i, i) = 1, since a length 1 string is a palindrome.

      3. P(i, j) = 2 + P(i + 1, j - 1) if i < j and s_i = s_j. (If the string begins and ends on the same character, it is always a good idea to use the first and last character in the palindrome.)

      4. P(i, j) = max(P(i + 1, j), P(i, j - 1)) if i < j and s_i ≠ s_j. (You cannot use both the first and last characters, so throw one of them away. Since it is not clear which one to throw away, try them both.)

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

         It is important to do the computations in an order so that values have already been computed when they are needed. Since the recurrence looks at smaller values of j and larger values of i, we fill in the array counting j up and i down.

           PalLen(s1...sn)
             P = nxn array
             for i = 1,...,n do
               P[i, i] = 1;
             for i = 2,...,n do
               P[i, i-1] = 0;
             for i = n-1,...,2 (count down)
               for j = i+1,...,n (count up)
                 if si == sj then
                    P[i, j] = 2 + P[i+1, j-1];
                 else
                    P[i, j] = max(P[i+1, j], P[i, j-1]);
             return P[1, n];
         

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

         It takes Θ(n²) time. There are about n²/2 entries to fill in, and each takes O(1) time.

   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).

      The algorithm does not work. It presumes that the first character must be used. What if the input string is abb? Then the longest palindromic subsequence is bb. But the given algorithm reports that it is a.