Homework 4 (assigned April 24, due May 1)

Reading: CLRS chapter 15, sections 15.1–15.4.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

"Do" Exercises (not to be handed in):

1. Exercise 15.3-4, page 390.

2. Exercise 15.4-5, page 397.

3. Problem 16-1, part d, page 447. Use dynamic programming.

Assigned Problems (to be handed in):

Important: When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.

1. The input to this problem is two words (strings of characters) X[1.. m] and Y[1.. n] of lengths m and n, respectively. The goal is to transform one word into the other as cheaply as possible using the following "edit" operations. For a cost of D we can delete any character. For a cost of I we can insert a character in any position. For a cost of R we can replace any character by any other character. For example, we can transform the string ALGORITHM into the string LOGARITHM as follows:
   ALGORITHM — LGORITHM — LOGORITHM — LOGARITHM
   The sequence of operations is delete, insert, replace.
   The edit-distance of two words is the minimum cost of edit operations needed to transform one word into the other. (If the above sequence of operations is optimal, then the edit-distance of ALGORITHM and LOGARITHM is D + I + R. If D = I = R = 1, then the edit-distance would be 3.)
   Give a dynamic programming algorithm that finds the edit-distance of two given words X[1.. m] and Y[1.. n] in O(mn) steps, where m and n are the respective lengths of the two input words.
   • Define the subproblem(s) to be solved. For full credit, define any variables you introduce. (5 points)
   • State the recurrence that solves the subproblems in terms of smaller subproblems. Include the solution of the base case (i.e., smallest subproblems). (5 points)
   • Write pseudocode for your algorithm. (4 points)
   • Analyze your algorithm's running time. (1 point)

2. You are given a string of n characters S[1.. n] from a text document in which all punctuation and spaces have been removed, so that the text looks something like "longagoinalandfaraway". You wish to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict( ⋅ ) such that, for any string w, dict(w) = 1 (true) if w is a valid word, and dict(w) = 0 (false) otherwise.
   Give a dynamic programming algorithm that determines whether an input string S[1..n] can be reconstituted as a sequence of valid words. Assume that calls to dict take unit time.
   • Define the subproblem(s) to be solved. For full credit, define any variables you introduce. (5 points)
   • Write a recurrence that solves the subproblems in terms of smaller subproblems. Do not forget the base case (i.e., smallest subproblems). (5 points)
   • Write pseudocode for your algorithm. (4 points)
   • Analyze the running time of your algorithm. (1 point)
   • If the string is valid, make your algorithm output the corresponding sequence of words. Does the running time of your algorithm increase as a result? (5 points)

3. A subsequence is a palindrome if it is the same whether read left to right to left. For example, the sequence
   A, C, G, T, G, T, C, A, A, A, A, T, C, G
   has many palindrome subsequences, including A, C, G, C, A, and A, A, A, A. On the other hand, the subsequence A, C, T is not a palindrome.
   Give a dynamic programming algorithm that takes an input sequence X[1.. n] over some alphabet and returns the length of the longest palindrome subsequence. The running time of your algorithm should be O(n²).
   • Define the subproblem(s) to be solved. (5 points)
   • State the recurrence that solves the subproblems in terms of smaller subproblems. Include the solution of the base case (i.e., smallest subproblems). (5 points)
   • Write pseudocode for your algorithm. (4 points)
   • Analyze the running time of your algorithm and justify its O(n²) time complexity. (1 point)