CSC 344
Homework 5
Assigned 20 April, due 4 May
The "change problem" is to take in a list (or array or
whatever) of positive integer coin denominations and a non-negative
integer value, and to return a list of coins (chosen from those
denominations) that add up to the specified value, using as few
coins as possible. As we've seen in class, the obvious greedy
algorithm doesn't work; consider
change(<1,17,25>,35).
Develop three versions of a program to solve the
"change problem":
- A simple recursive implementation based on the pseudocode given in
class.
- A memo-ized version of the same recursive implementation. This
should produce exactly the same results, but take significantly less
time.
- A dynamic-programming version, which fills in the same table from
the bottom up rather than on-demand from the top down. This too should
produce exactly the same results.
Run all three programs with a reasonable selection of test cases, to
confirm that they're all correct. Choose test cases of a variety of
sizes, and run each program on the same test cases to find out which
takes the least time.
Last modified:
Tue Apr 27 16:27:16 EDT 2004
Stephen Bloch / sbloch@adelphi.edu