EECS 215 Dynamic Programming Problems

Write a program to solve two of the following problems using dynamic programming. Also, solve one of the same problems using brute-force exhaustive search. Compare the running times of your dynamic programming solution to the brute-force solution for as large a problem as you are willing to wait for on the slower implementation.

1) 6.4. You are given a string of n characters S[1 . . . n], which you believe to be a

corrupted text document in which all punctuation has vanished (so that it looks

something like “itwasthebestoftimes...”). You wish to reconstruct the document

using a dictionary, which is available in the form of a Boolean function lookup(string word) that returns true only if the word is in the Unix Dictionary (You may use your AVL tree from homework 1).

a) Give a dynamic programming algorithm that determines whether the string S can be reconstituted as a sequence of valid words. The running time should be at most O (N2 * lg N ), assuming calls to lookup take Theta (lg M) time where M is the number of words in the dictionary.

b) In the event that the string is valid, have your algorithm output the

b) corresponding sequence of words.

Input: a series of lines for S.

Output: The sentences broken into proper words, or the word No if the string is not a valid sentence.

2) 6.8. Given two strings x = x1 x2 · · · xn and y = y1 y2 · · · ym, we wish to find the length

of their longest common substring, that is, the largest k for which there are

indices i and j with xi xi +1 · · · xi +k−1 = y j y j +1 · · · y j +k−1 . Show how to do this in

time O (mn).

Input: pairs of strings for x and y – one on each line.

Output: the longest common substring.

3) 6.14. Cutting cloth. You are given a rectangular piece of cloth with dimensions X × Y ,

where X and Y are positive integers, and a list of n products that can be made

using the cloth. For each product i ∈ [1, n] you know that a rectangle of cloth of

dimensions ai × bi is needed and that the final selling price of the product is c i .

Assume the ai , bi , and c i are all positive integers. You have a machine that can

cut any rectangular piece of cloth into two pieces either horizontally or

vertically. Design an algorithm that determines the best return on the X × Y

piece of cloth, that is, a strategy for cutting the cloth so that the products made

from the resulting pieces give the maximum sum of selling prices. You are free to

make as many copies of a given product as you wish, or none if desired.

4) 6.17. Given an unlimited supply of coins of denominations X1 , X2 , . . . , XN, we wish to

make change for a value V; that is, we wish to find a set of coins whose total

value is V. This might not be possible: for instance, if the denominations are 5

and 10 then we can make change for 15 but not for 12. Give an O (NV)

dynamic-programming algorithm for the following problem.

Input: X1 , . . . , XN; V.

Question: Is it possible to make change for V using coins of

denominations X1 , . . . , Xn? If so, give the change given.

5) 6.19. Light Pockets problem.

I like to get rid of as many coins as possible when making a purchase of total cost T. Given a specified supply of coins in the format P N D Q O (for penny, nickel, dime, quarter, and ones) and a total cost of item T, we wish to pay for the purchase using the most coins possible; that is, we wish to find a set of k coins whose total value is v such that the number of coins left in my pocket is minimal. Note you will always have plenty of one dollar bills to use, but you will get change back whenever you use a dollar and there is change due. Give an efficient dynamic-programming algorithm for the following

problem.

Input: a series of lines, each with 6 integers representing a problem of the form: P N D Q O T

Question: What should I spend to pay for my purchase of cost T?