Homework 7

CS409 - Spring 2000

Due: Thursday, Mar 30

1. (10 pts) Do problem 3.5 on page 78 of Skiena.

    

2. (10 pts) Do problem 3.6 on page 78 of Skiena.
   Hints: Use dynamic programming. You should assume that there is a 1 cent coin (d₁ = 1), so for any amount n there is always a way to choose coins to make that amount. Your algorithm should run in time O(nk) where n is the amount for which we are attempting to find change and k is the number of coin denominations. You may assume that the goal is simply to report the optimum number of coins rather than to produce a list of the coins used to achieve this optimum.  Explain your algorithm and analyze its running time. Your answer should be brief and it should be clearly expressed using a mix of English and pseudo-code. Answers that are unclear or excessively long will be penalized.

    

3. (10 pts) Do problem 3.9 on page 79 of Skiena.

    

4. (10 pts) Do problem 3.10 on page 79 of Skiena.