Homework 5 (assigned May 1, due May 8)

Reading: CLRS chapter 22, sections 22.1–22.2. Reading for next week's lecture: chapter 22, sections 22.3–22.5; chapter 24, section 24.3.

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.1-4, page 370.

2. Problem 15-9, page 410.

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. In class we saw that dynamic programming solutions can be implemented in two distinct ways — iteratively or recursively. A recursive implementation of a dynamic programming solution is referred to as "memoization".
   1. Write a memoized version of a dynamic programming solution to the coin change problem (HW 3, assigned problem 3). (4 points)
   2. Write a memoized version of a dynamic programming solution to the longest palindrome subsequence problem (HW 4, assigned problem 3). (6 points)

2. You are given an array A[1 .. n] of n positive real numbers that represent the price of a given stock over n consecutive days, numbered i = 1, 2, …, n. For each day i, we have a price A[i] per share for the stock on that day. (Assume for simplicity that the price was fixed during each day.) You want to know: how should we choose a day i on which to buy the stock and a later day j > i on which to sell it if we want to maximize the profit per share, A[j] − A[j]? If there is no way to make money during the n days, your algorithm should conclude this instead. Give an O(n)-time dynamic programming algorithm to find the optimal numbers i and j.
   • Define the subproblem. For full credit, define any variables you introduce. (4 points)
   • Write a recurrence that expresses the optimal solution of the subproblem in terms of the optimal solution of smaller subproblems. Solve the base case (i.e., smallest subproblems). (5 points)
   • Write pseudocode for your algorithm. (4 points)
   • Argue that your algorithm is correct. (1 point)
   • Analyze the running time of your algorithm. (1 point)

3. 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 the strings "ABABC" and "BABCA" is string "BABC" of length 4. Other common substrings are "AB", "BC", and "BA". Let n = |X| and m = |Y|. Give a Θ(nm) dynamic programming algorithm to find the length of the longest common substring of X and Y.
   • Define the subproblem. (4 points)
   • Write a recurrence that expresses the optimal solution of the subproblem in terms of the optimal solutions of smaller subproblems. Solve the base case (i.e., smallest subproblems). (5 points)
   • Write pseudocode for your algorithm. (4 points)
   • Analyze the running time and space requirements of your algorithm. Suggest how the asymptotic space requirements can be reduced. (2 points)

4. Suppose you are given an n × n bitmap, represented by an array M[1 .. n, 1 .. n] whose entries are zeros and ones. An all-ones square is a subarray of the form M[i .. i′, j .. j′] in which every bit is equal to 1. You wish to find the size of the largest all-ones square.
   Example:
   In this example, the answer is 3, since the largest all-ones square has size 3 × 3. There are three 3 × 3 all-ones square subarrays in this example. One is shown below by underlines, another is shown in a box, and another is indicated by italics.
   Give an O(n²)-time dynamic programming algorithm to find the maximum size of an all-ones square in M. You do not need to locate such a largest all-ones square in the array; you only need to determine its size.
   • Define the subproblem. (5 points)
   • State the recurrence that expresses the optimal solution of the subproblem in terms of the optimal solution of smaller subproblems. Solve 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)
   • Now modify your algorithm to return the location of a maximum all-ones square. (5 points)

   ---

   Gerry Brady
   Wednesday May 1 01:48:13 CDT 2013