Homework 7 (assigned May 13, revised May 19; due May 20)

Reading: CLRS 22.1-22.3; CLRS 23.1-23.2.

Written assignment: Solve the following exercises and problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both exercises and problems.

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

1. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For example, if S is 5, 15, -30, 10, -5, 40, 10 then 15, -30, 10 is a contiguous subsequence but 5, 15, 40 is not. Design a dynamic programming algorithm for the following task:
           Input: A list of numbers, a₁, a₂, ..., a_n.
           Output: The contiguous subsequence of maximum sum. (A subsequence of length 0 has sum zero.)
   For the example above, the answer is 10, -5, 40, 10, with a sum of 55.

2. Exercise 15.4-5 on CLRS page 356. Can you improve the running time to O(n log n)? If so, how?

Problems (to be handed in):

1. Longest common subsequence
   Exercises 15.4-2 on CLRS page 356. (10 points)

2. Coin changing problem
   Design a dynamic programming algorithm for the following version of the coin changing problem:
   Given an unlimited supply of coins of denominations d[1], d[2], ..., d[n], we wish to make change for an amount A, that is, we wish to find a set of coins whose total value is A. This might not be possible; for instance, if the denominations are 5 and 10, then we can make change for 15 cents but not for 12. Write an O(nA) dynamic programming algorithm to solve the following problem.
           Input: Positive integers d[1], d[2], ..., d[n]; another positive integer A.
           Output: Is it possible to make change for A using coins of denominations d[1], d[2], ..., d[n]?
   (20 points)

3. String reconstruction problem
   You are given a string of n characters S[1..n], which you believe to be a corrupted text document in which all punctuation and spaces have been removed, so that the string looks something like "itwasthebestoftimes". You want to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict:
           For any string w, dict(w) = true if w is a valid word
   = false otherwise
   1. Write a dynamic programming algorithm that determines whether the string S[1..n] can be reconstituted as a sequence of valid words. The running time of your algorithm should be at most O(n²), assuming calls to dict take unit time. (20 points)
   2. In the event that the string is valid, make your algorithm output the corresponding sequence of words. (10 points)

4. Edit-distance problem
   We wish to change one string of text X[1..m] to another string Y[1..n]. We do the transformation by starting with X and repeatedly modifying it by either inserting a character, deleting a character, or replacing one character by another. Let the cost of an insertion be I, the cost of a deletion be D, and cost of a replacement be R, and assume these costs are independent of the length of the string. As an example, assume I = 5, D = 3, and R = 1, and we are to change "blue" to "white". One way to perform the transformation is as follows:

   Operation	String	Cost
   initial string	blue	0
   Replace	wlue	1
   Replace	whue	1
   Replace	whie	1
   Insert	white	5

   The total cost is 8.
   1. Write a dynamic programming algorithm to transform X[1..m] to Y[1..n] with minimum cost. You may assume that m ≥ n, but you should see if there are any easy ways to solve the problem without that assumption. Do NOT assume that I = 5, D = 3, and R = 1. Your algorithm should work for any costs I, D, and R. Analyze the running time of your algorithm. (20 points)
   2. Find the edit-distance between "algorithm" and "logarithm".   Let I = D = 1; and R = 1 if X[i] ≠ Y[j] and R = 0 otherwise. (5 points)
   (See also Problem 15-3, CLRS pp. 364-367.)

5. Greedy technique
   Consider the problem of scheduling n jobs of known durations t₁, t₂, ..., t_n for execution on a single processor. The jobs can be executed in any order, one job at a time. Your goal is to find a schedule that minimizes the total time spent by all the jobs in the system. The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.
   1. Design a greedy algorithm that solves this problem. Each job must run nonpreemptively, that is, once job i is started, it must run continuously for t_i units of time. (15 points)
   2. Prove that your algorithm always yields an optimal solution and state the running time of your algorithm. (15 points)