Homework 7
CS409 - Spring 2000
Due: Thursday, Mar 30
- (10 pts) Do problem 3.5 on page 78 of Skiena.
- (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
(d1 = 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.
- (10 pts) Do problem 3.9 on page 79 of Skiena.
- (10 pts) Do problem 3.10 on page 79 of Skiena.