Problem 1. A student once told me he enjoyed designing role-playing board games that involved rolling a large number of weird dicewhich may have 6, 12, 20, or other numbers of sides. His question was how to determine the chance of rolling R when rolling a handful of weird dice. Let the numbers of sides of the k dice be s1, s2, s3, , sk. What is the number of different ways you can roll R with the k dice?

(Hint: what would you like to ask the oracle with respect to rolling the first k-1 dice?)

Problem 2. Show how the dynamic programming algorithm would be used bottom-up to make change in the amount of 25 cents, when the coins available are worth 1, 7, 9, and 11 cents. Show the table that would be generated. How would your answer change if we were to use the memoization approach instead of bottom-up? What is the runtime of the algorithm for making change for N cents with 4 coin types?