Youve just signed up as a software engineer for a new intergalactic trading post in Deep Space 6. For each transaction, you are given a list of coin denomination values, e.g., denomination = [1, 5, 10, 17], and an amount of change, C. You have an unlimited number of each type of coin. Your goal is to find the shortest possible list of coins that adds up to C. For simplicity, assume that there is always a penny 1 ? denomination and that the desired change C is an integer, so the problem always has a solution.

(a) Clearly state the set of subproblems that you will use to solve this problem.

(b) Write a recurrence relating the solution of a general subproblem to solutions of smaller subproblems.

(c) Analyze the running time of your algorithm, including the number of subproblems and the time spent per subproblem. You should end up with a pseudopolynomial running time, meaning that the polynomial includes some power of C. This is not exactly the same as being polynomial with respect to the size of the input, because it only takes lg C bits of input to represent the number C.

(d) Download _change.zip. Write a function make_change(denomination, C) which returns a list of coins that add up to C, where the size of the list is as small as possible. Write it in a bottom-up manner (because the Python recursion stack is limited). Note that, assuming your subproblems from part (a) only find the size of the best result, you should also keep parent pointers so that you can reconstruct the actual subsequence.

change.py

#!/usr/bin/python def make_change(denominations, C): return 'NOT_IMPLEMENTED'

*****tester*****

#!/usr/bin/python import unittest import sys import time import change class TestChange(unittest.TestCase): def test1_small(self): """small tests"""  self.change_test([1, 5, 10, 17], 0, 0) self.change_test([1, 5, 10, 17], 4, 4) self.change_test([1, 5, 10, 17], 5, 1) self.change_test([1, 5, 10, 17], 34, 2) self.change_test([1, 5, 10, 17], 33, 4) def test2_large(self): """large test"""  denominations = [1, 2896, 9274, 8063, 1764, 5375, 4228, 7611, 1482, 816, 9335, 2582, 4672, 649, 1405, 5362, 1790, 4774, 9978, 3175, 6091, 1302, 9683, 728, 9819, 1934, 863, 1828, 2680, 8911, 3065, 1010, 182, 2167, 4443, 7111, 493, 262, 5091, 3337, 3956, 3646, 244, 161, 9966, 7784, 3105, 7470, 2688, 1894, 4561, 9924, 557, 8192, 7142, 4046, 8344, 6368, 7391, 7459, 395, 2680, 5844, 376, 183, 7622, 537, 5526, 371, 4769, 4498, 4452, 2727, 3929, 600, 2633, 8090, 3829, 4186, 135, 1847, 9421, 9110, 3429, 2633, 1423, 78, 4059, 9877, 2749, 7422, 5200, 9310, 49, 3456, 9770, 7729, 7724, 1175, 7743, 8492] C = 100000 self.change_test(denominations, C, 11) def change_test(self, denominations, C, answer_size): coins = change.make_change(denominations, C) total = 0 for coin in coins: self.assertTrue(coin in denominations) total += coin self.assertEqual(C, total) self.assertEqual(answer_size, len(coins)) if __name__ == '__main__': unittest.main(argv = sys.argv + ['--verbose'])