Objectives

The objective of PA5 is to create a program that counts the number of ways a certain integer amount of money can be paid using a certain coin set, see the lectures on dynamic progging in general and the coinsPA lecture specifically. Write two functions, mkChangeDC, a recursive, divide and conquer solution, and mkChangeDP, a dynamic programming solution. Apart from returning the number of ways, mkChangeDC must count the number of recursive calls in a global variable calls, and mkChangeDP must count the number of dynamic programming table reads in a global variable reads.

Download the following file, mkChange.txt and rename it mkChange.py.

Testing and Checkin

When provided with coins.txt:
python3 mkChange.py 5000 coins.txt
should produce:
mkChangeDC
amount: 5000 coins: [1, 5, 10, 25] ways: 16892551 calls: 16943154
mkChangeDP
amount: 5000 coins: [1, 5, 10, 25] ways: 16892551 reads: 4259203
although the number of calls or reads may vary. Check in your mkChange.py code.

The Checkin tab on the course website will perform preliminary testing of your code. These tests do not indicate your final grade. They can, however, catch mistakes in your submission. You can re-submit your file as often as you want.