Homework 5 (assigned October 27, due November 2)

Reading: CLRS chapters 9 and 15. Reading for next week's lecture: CLRS chapter 22.

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. The following problem asks you to develop a dynamic programming algorithm to find the longest monotonically increasing subsequence within a sequence of n numbers.
   • Construct a recurrence that computes the length of the longest monotonically increasing subsequence, given an sequence of n integers. Hint: Consider the length of a longest increasing subsequence ending exactly at position i.
   • Use your recurrence to construct an algorithm to find the length of a longest longest monotonically increasing subsequence of an input sequence of n integers. Find a smallest subproblem to start with and use your recurrence to fill out your DP table.
   • What is the time complexity of your algorithm?
   • Given input S = [22, 5, 7, 2, 23, 10, 15, 21, 3, 17], use your algorithm to find the length of a longest monotonically increasing subsequence of S.
   • What auxiliary information does your algorithm need to store in order to reconstruct the actual subsequence instead of its length?

2. You are given an array A[1..n] of n integers, not necessarily positive. Your goal is to find two indices i and j such that the sum of the array entries from A[i] to A[j] is maximum.
   • What is the time complexity of an algorithm that tries all substrings of length 1, length 2, …, length n and takes the largest of all of these sums?
   • From dynamic programming, we have learned to store previous computations in a table to save time. Using this idea, what would be the space requirement of the algorithm above?
   • Consider the following algorithm. Scan the input array from left to right and keep track of two quantities: the maximum sum so far and the maximum sum ending at position i. Design an algorithm based on this idea. What is the running time of this algorithm?

3. You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts m₁ < m₂ < … < m_n, where each m_i is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel, at distance m_n, which is your destination. You would like to travel 200 miles a day, but this may not be possible, depending on the spacing of the hotels. If you travel x miles during a day, the penalty for that day is (200 − x)². You want to plan your trip so as to minimize the total penalty, i.e., the sum, over all travel days, of the daily penalties. Give an dynamic programming algorithm that determines the optimal sequence of hotels at which to stop.
   • State the dimensions of your dynamic programming table and define in English the meaning of an entry (subproblem) in your table.
   • State the recurrence for entries of your table in terms of smaller subproblems.
   • Write the solution to the base case.
   • Write pseudocode for an algorithm to fill the remaining entries of your table.
   • Analyze the running time of your algorithm, including the number of subproblems and the time spent per subproblem.

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 longest common substring (not subsequence) of two strings X and Y is the longest string that appears as a run of consecutive letters in both strings. For example, the longest common substring of PHOTOGRAPH and TOMOGRAPHY is OGRAPH.
   Given two strings X = x₁x₂…x_n and Y = y₁y₂…y_m , find the length of their longest common substring, i.e., the largest k for which there are indices i and j with x_i…x_{i + k − 1} = y_j…y_{j + k − 1}. Give a O(nm) dynamic programming algorithm to solve this problem. The strings X and Y are given as arrays of characters.
   • Define in English the meaning of the subproblem(s) that you will use to solve this problem. (2 points)
   • Write a recurrence for the value of an optimal solution of your subproblem in terms of smaller subproblems. Write the solution to the base case(s) (i.e., smallest subproblems). (3 points)
   • Write pseudocode for your algorithm. (3 points)
   • Use your algorithm to find the length of a longest common substring of X = [a, b, c, d, b, c, d] and Y = [a, b, c, h, b, c, d]. Show your dynamic programming table. (2 points)

2. Solve the knapsack problem for the following input values using the dynamic programming knapsack algorithm from class: w = [6, 3, 4, 2], v = [30, 14, 16, 9], W = 10.
   • Show your output table. What is the maximum value of an optimal subset? (5 points)
   • Write pseudocode for an algorithm that finds the items in an optimal subset from the output table generated by the knapsack problem DP algorithm. What is the running time of your algorithm? (10 points)
   • Use your algorithm to find the items included in an optimal subset using your output table. Show your work. (5 points)

3. The edit distance d(x, y) of two strings of text, x[1..m] and y[1..n], is defined to be the minimum possible cost of a sequence of "edit" operations (defined below) that transforms string x[1..m] into string y[1..n]. To define the effect of the edit operations, we use an auxiliary string z[1..s] that holds the intermediate results. At the beginning of the transformation sequence, s = m and z[1..s] = x[1..m], i.e., we start with string x[1..m]. At the end of the transformation sequence, we should have s = n and z[1..s] = y[1..n]. Throughout the transformation, the current length s of string z is updated as part of each operation.
   Each "edit" operation may alter the string z and its size s. Each "edit" operation also has an associated cost. The cost of a sequence of "edit" operations is the sum of the costs of the individual operations in the sequence. The goal of the edit-distance problem is to find a sequence of "edit" operations of miminum cost that transforms x[1..m] into y[1..n].

   We define three edit operations:

   Operation	Cost	Effect
   replace(i, c)	6	replace the character at position i with the character c by setting z[i] = c
   delete(i)	5	delete the character at position i by setting z[i..s] = z[i + 1..s] and decrementing s
   insert(i, c)	5	insert the character c into string z at position i by setting z[i + 1..s + 1] = z[i..s], z[i] = c, and incrementing s.

   • Describe a dynamic programming algorithm that, given two strings x[1..m] and y[1..n], computes the edit distance from x[1..m] to y[1..n] using the three edit operations and edit costs defined above and prints an edit operation sequence.
     • Define the subproblems you will use to solve this problem. (5 points)
     • Write a recurrence relating the solution of a general subproblem to solutions of smaller subproblems. (5 points)
     • Describe your algorithm in pseudocode. (5 points)
     • Analyze the running time and space requirements of your algorithm. (5 points)
   • Use your algorithm to transform "blue" to "white". What is the cost d(blue, white)? Give the sequence of edit operations and their cost. (5 points)

4. You are a consultant. Your basic decision, each week, is whether to take a low-stress job or a high-stress job. If you select a low-stress job in week i, then you get a revenue of l[i] > 0 dollars; if you select a high-stress job in week i, you get a revenue of h[i] > 0 dollars. However, in order to take a high-stress job in week i, it is necessary that you do no job of either type in week i − 1. On the other hand, you can take a low-stress job in week i even if you have done a job of either type in week i − 1.
   Given a sequence of n weeks, a plan is specified by a choice of "low-stress", "high-stress", or "none" for each of the n weeks, with the property that if "high-stress" is chosen for week i > 1, then "none" has to be chosen for week i − 1. (You can choose a high-stress job in week 1.) The value of the plan is determined as follows: for each i, you add l[i] to the value if you choose "low-stress" in week i, and you add h[i] to the value if you choose "high-stress" in week i. You add 0 if you choose "none" in week i.

   Problem. Given sets of values l[1], l[2], …, l[n] and h[1], h[2], …, h[n], give a dynamic programming algorithm that finds the value of an optimal plan, i.e., a plan of maximum value. Your algorithm should run in O(n) time.

   • Define the subproblems that you will use to solve this problem. (5 points)
   • State the recurrence that expresses the value of an optimal solution of a subproblem in terms of smaller subproblems. Solve the base case(s) (i.e., smallest subproblems). (5 points)
   • Write pseudocode for your algorithm. (5 points)
   • Analyze the running time of your algorithm: what is the number of subproblems and what is the time spent per subproblem? (2 points)
   • What is the solution of the original problem in terms of solutions of your subproblems? Reconstruct the sequence of jobs. (3 points)
   • Suppose n = 4, and the values of l[i] and h[i] are given by the following table. Use your algorithm to find the plan of maximum value. What is the value of this plan? Show your work. (5 points)

     	Week 1	Week 2	Week 3	Week 4
     l	10	1	10	10
     h	5	50	5	1