Learning Outcomes

Students will be able to (1) employ the methodology of top-down dynamic programming using recursion and memoization, (2) employ the methodology of bottom-up dynamic programming, and (3) explain the kinds of savings in compute-time offered by the methodology of dynamic programming.

Reading

Read this article on Dynamic Programming and this article on Dynamic Programming and browse the section on Dynamic Programming on Geeks for Geeks.

Activities

You’ve found yourself in a post-apocalyptic world with no Apple Pay, no Bitcoin, and no credit cards. No paper money either. People use... big, heavy, coins. Coins are heavy so one of the more important reasons for computation in this society is to minimize the number of coins that comprise a given amount. Each region in this world has its own set of monetary units. One region has units of 1, 29, and 493 (sounds like 🧙right?). Another has 1, 4, 5, and 7. Another has 1, 11, 13, 29, and 31. Can you figure out the minimum number of coins for a given amount for any set of coin denominations?

Initialize a repository

As in the previous labs, go to GitHub, select Import Repository. Then:

For Your old repository’s clone URL

Enter https://github.com/rtoal/cmsi-186-lab-6-starter-code

For Your new repository details

Enter the repository name cmsi-186-lab-6.

The import might take a few minutes. When done, clone the repo and get ready to work.

Implement the coin changing methods

The starter code has two classes:

• CoinChanger.TopDown
• CoinChanger.BottomUp

Each has a minCoins method for you to complete. minCoins($a$, $\{d_1...d_n\}$) is to return the minimum number of coins, total, to make the amount $a$ given the set of coin denominations $\{d_1...d_n\}$. For example:

  minCoins(8, {1, 4, 5}) ⇒ 2
                        // two 4-cent coins

  minCoins(600, {1, 29, 493}) ⇒ 24
                        // one 493-cent coin,
                        // three 29-cent coin,
                        // twenty 1-cent coins

If minCoins is called without a 1-unit denomination, throw an error. If any one of the denominations are zero or negative, throw an error.

Now here’s the thing. Coin changing, if done “brute-force”, that is, by trying all possibilities, can take forever. In this lab, you are going to practice Dynamic Programming, a way of solving optimization problems more quickly than by trying all possibilities. During lecture, we will learn how dynamic programming can proceed top-down or bottom-up. You will implement both approaches, and study which one is better under which conditions. This is, after all, a laboratory assignment!

Perform experiments

Based on your understanding of top-down and bottom-up dynamic programming, determine in what kinds of scenarios the top-down approach should be faster and in which scenarios bottom-up should be faster. Write up your thoughts, but also run timing studies on the methods you wrote. What kinds of scenarios should you consider? It’s up to you, but you might want to think about large vs. small amounts (relative to the denominations), wide vs. small gaps between denominations, large vs. small sets of denominations, and so on.

In this lab, you do not need any main methods. For your experiments, use JShell!

Test as you go

A single unit test suite combining tests for both of your methods is provided in the starter code. Use it as follows:

$ javac CoinTest.java && java CoinTest

Stretch Challenge (Optional)

This lab only requires you to compute the minimum number of coins that make up a certain amount. You may wish to try to add additional methods that tell you how many of each type of coin are present in this minimal coin set. For example:

  minimalCoinSet(8, {1, 4, 5}) ⇒ {4: 2}
                      // two 4-cent coins

  minimalCoinSet(600, {1, 29, 493}) ⇒ {493: 1, 29: 3, 1: 20}
                      // one 493-cent coin,
                      // three 29-cent coin,
                      // twenty 1-cent coins

Begin working on the challenge after finishing up the assigned work. There will be no extra credit awarded for this challenge; complete it for your own personal satisfaction, if you have the time and energy.

What to turn in

Online:

• Your repo, cmsi-186-lab-6, should have each of the starter Java classes completed, as well as the test files from the starter code unchanged. Please make sure the code is beautiful, with well-chosen names, perfect formatting, and appropriate comments (if called for). Don’t forget to update the README.

On hardcopy or email:

1. A writeup of the lab experiment described above.
2. Did you choose a HashMap or a TreeMap (or some other kind of map)? Why did you make that choice?
3. What solution, top-down or bottom-up, appealed to you more and why? (There is no right or wrong answer to this, as it asks for your personal opinion only.)
4. (Optional) Feel free to let me know what you liked/disliked about this lab, what you learned, etc.