Dynamic Programming Algorithms

Directions: Some of the questions on this assignment will appear on the quiz on Wednesday, May11th.

Recall that a complete dynamic program is specified by the following four pieces of information:

The precise definition for what cell i or cell (i; j) of your table holds.

The formula for how to fill in the cells of your table. The base cases for your cells.
The specific cell that holds the solution.


    1. Consider the following generalization of the Activity Selection Problem: You are given a set of n activities each with a start time si, a finish time fi, and a weight wi. Design a dynamic programming algorithm to find the weight of a set of non-conflicting activities with maximum weight.

    2. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For in-

stance, if S = f5; 15; 30; 10; 5; 40; 10g then f15; 30; 10g is a contiguous subsequence but f5; 15; 40g is not. Give a dynamic programming algorithm for the following task: You are given a list of numbers, fa1; a2; : : : ; ang. You should return the contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10; 5; 40; 10, with a sum of 55.

    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 a1 < a2 < < an, where each ai 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 an), which is your destination. You would ideally like to travel

300 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 (300 x)2. You want to plan your trip so as to minimize the total penalty-that is, the sum, over all travel days, of the daily penalties.

Give a dynamic programming algorithm to determine the penalty for the optimal sequence of hotels at which to stop.

    4. Firestones is considering opening a series of restaurants along Highway 1. The n possible locations are along the highway, and the distances of these locations from the downtown San Luis Obispo are, in miles and in increasing order, m1; m2; :::; mn. The constraints are:

At each location, Firestones may open at most one restaurant. The expected profit from opening a restaurant at location i is pi, where pi > 0 and i = 1; 2; : : : ; n.

Any two restaurants must be at least k miles apart, where k is a positive integer.

Give a dynamic programming algorithm to compute the maximum expected total profit subject to the given constraints.

5. Given two strings x = x1x2    xn and y = y1y2    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 xixi+1    xi+k  1 =
yj yj+1    yj+k  1.

For example, if x = dcabagc and y = cbcbcabca, then the longest common substring is cab with length 3.

Give a dynamic program to determine the length of the longest common substring of two strings, x and y.


1 of 2 
    6. When a new gene is discovered, a standard approach to understanding its function is to look through a database of known genes and find close matches. The closeness of two genes is measured by the extent to which they are aligned. To formalize this, think of a gene as being a long string over an alphabet = fA; C; G; T g. Consider two genes (strings) x = AT GCC and y = T ACGCA. An alignment of x and y is a way of matching up these two strings by writing them in columns, for instance:

-    A    T    -    G    C    C

T    A    -    C    G    C    A

Here the “-” indicates a “gap”. The characters of each string must appear in order, and each column must contain a character from at least one of the strings. The score of an alignment is specified by a scoring matrix of size (j j + 1) (j j + 1), where the extra row and column are to accommodate gaps. For instance the preceding alignment has the following score: ( ; T ) + (A; A) + (T; ) + ( ;C);+ (G;G)+ (C;C)+ (C;A)

Give a dynamic programming algorithm that takes as input two strings x[1 : : : n] and y[1 : : : m] and a scoring matrix , and returns the highest scoring alignment.

    7. Consider the following task: You are given a set of n positive integers, fa1; a2; : : : ang and some positive integer k. Give a dynamic programming algorithm to determine if there is some subset of the ai’s that adds up to k.

    8. 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 2 [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 ci. Assume the ai; bi, and ci are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design a dynamic programming 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.

    9. 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 a dynamic programming algorithm for the following problem: You are given x1; : : : ; xn; v. You must answer the following question: Is it possible to make change for v using coins of denominations x1; : : : ; xn?

    10. Consider the following variation on the change-making problem: you are given denominations x1; x2; : : : ; xn, and you want to make change for a value v, but you are allowed to use each denomination at most once. For instance, if the denominations are 1, 5, 10, 20, then you can make change for 16 = 1 + 15 and for 31 = 1 + 10 + 20 but not for 40 (because you can’t use 20 twice).

You are given positive integers x1; x2; : : : ; xn; v. Can you make change for v, using each denomination xi at most once?

Show how to solve this problem in time O(nv).
















2 of 2