Description
Question 1. (10 points) Exercise 1 from Chapter 6, pages 312-313 of the textbook.
Question 2. (10 points) Suppose you visit a country where the coins are of denominations d1, d2, . . . , dn
and you wish to make change for value v. Provide an efficient dynamic programming algorithm
for calculating the minimum number of coins required to make change for value v. For example, if
the coin denominations are 1, 2, 5, and 7, then you would need at least 2 coins (i.e., 5, 5) to make
change for value 10. You may assume that the coin denominations are such that it is possible to
make exact change for any value.
Question 3. (10 points) Suppose that you run a fast-food restaurant business and wish to open
a series of restaurants along a highway. There are n possible locations along the highway where
you could open your restaurants, and these n locations are at distances of m1, m2, . . . , mn miles,
in increasing order, from the starting point of the highway. The expected profit from opening a
restaurant at location i is pi
, where pi > 0 and 1 ≤ i ≤ n. Give an efficient algorithm to compute
your maximum expected total profit, subject to the following two constraints: (i) You can open
at most one restaurant at each location, and (ii) any two restaurants must be at least k miles
apart along the highway, where k is a positive integer.
Question 4. (10 points) Exercise 5 from Chapter 6, pages 316-317 of the textbook.
Question 5. (10 points) Exercise 11 from Chapter 6, page 323 of the textbook.