The Coin Change Problem

How many ways can you make change for a dollar?

You could use 100 pennies. You could use two half-dollars. You could use three quarters, two dimes, and one nickel. You could use one quarter, two dimes, four nickels, and 35 pennies.

And so on and so forth. It’s easy to see that there are a lot of ways to make change for a dollar. But, for any given amount of money, there is a conceptually simple — and clever — way to compute the number of ways that you can make change for it.

Let’s say that there is a list of coin denominations, and you can choose from each denomination as many coins as you need. So, in this case, we have two half-dollars, four quarters, ten dimes, 20 nickels, and 100 pennies. Those are all the coins that you need.

For any given amount of money, the number of ways to make change for it is just the number of ways to make change for it using the first denomination on the list, plus the number of ways to make change for it without using the first denomination on the list.

We are applying a divide-and-conquer strategy. You divide the problem into subproblems until you get problems that are trivially solvable. Then, to produce a solution to the original problem, you combine all of the solutions to the subproblems.

So, for example, our problem is to compute the number of ways to make change for a given amount of money. We divide that problem into two subproblems:

(1) Compute the number of ways to make change for the amount of money using the first denomination in our list of denominations

(2) Compute the number of ways to make change for the amount of money without using the first denomination in our list

If it’s trivial to solve a subproblem, then solve it. If it’s not trivial to solve, then divide it into two subproblems of its own.

Two parameters define the coin change problem: (1) the amount of money that you must make change for and (2) the list of coin denominations. So, you can reduce the size of a problem instance in two ways: (1) You can decrease the amount of money that you must make change for, and (2) you can shorten the list of coin denominations.

Option (1) corresponds to subproblem (1). When you use the first denomination in the list, you decrease the amount of money that you must make change for. So, for example, let’s say that you must make change for one dollar and you decide to use a half-dollar, the first denomination in your list of denominations. Now that you’ve put in a half-dollar, you just have to make change for 50 cents. So, you’ve decreased the amount of money that you must make change for.

Option (2) corresponds to subproblem (2). If you don’t use the first denomination in your list of denominations, then you effectively shorten your list of denominations. For example, let’s say that your list of denominations is {half-dollars, quarters, dimes, nickels, pennies}. If you decide not to use half-dollars, then your list of denominations effectively becomes {quarters, dimes, nickels, pennies}.

You continually reduce the size of your problem until you finally reach instances of the problem that are trivially solvable. These are the trivial instances of the coin change problem:

-You must make change for no amount of money. There is one way to solve that problem: You use no coins.
-You must make change for a negative amount of money. There is no way to do that.
-You must make change for some amount of money, but there are no denominations to choose coins from. In this case, too, there are zero ways to make change.

You solve these problems and then combine them to create a solution to the original problem. In this case, you combine them through addition. The number of ways to make change for some amount of money is the number of ways to make change for it using the first denomination on the list, plus the number of ways to make change for it without using the first denomination on the list.

The subproblems are the same type of problem that the original problem is, because the subproblems require you to compute the number of ways to make change for a given amount of money, too. So, we apply the same problem-solving procedure to the subproblems that we do to the original problem. Consequently, it is natural to deploy a recursive algorithm, as it was when I implemented a solution to the Towers of Hanoi problem.

I decided to employ recursion, and I implemented the algorithm in Scheme.

Notice that this is a top-down approach to solving problems. You start with a problem and divide it into smaller and smaller pieces, working your way down until you arrive at pieces that are trivially solvable.

But you don’t have to approach our problem in a top-down way. Instead you can employ a bottom-up approach, where you start with the solutions to the smallest subinstances of the problem and continually build on them until you get up to a solution to the whole problem.

Because the top-down, recursive approach typically has to process a lot of the same subinstances and the bottom-up approach does not, the bottom-up approach is typically a lot faster. For example, in this case, the bottom-up approach is O(D * M), where D is the number of coin denominations and M is the amount of money (in cents). In contrast, if you don’t memoize the recursive solution, it runs in exponential time.

As I have in the past, I used dynamic programming to design just such a bottom-up strategy. (That program also features a naive recursive solution and a memoized recursive solution.)

To find the maximum independent set of any tree, I also designed a bottom-up, dynamic-programming algorithm and implemented a top-down, recursive algorithm.

The approaches to the maximum independent set problem feature a technique that the approaches to the coin change problem also feature: The use of inclusion and non-inclusion to neatly divide the problem into just two subproblems. So, the maximum independent set of a tree either includes the root of the tree or it doesn’t include the root of the tree. Exploiting that fact, you construct the independent set that includes the root and the independent set that doesn’t include the root, and then you take the larger of the two. Likewise, to count the total number of ways that you can make change for some amount of money, you count the number of ways that you can make change for it if you include the first denomination on the list and the number of ways that you can make change for it if you do not include the first denomination on the list.

I have found that many dynamic programming approaches feature this technique. For example, an approach to the discrete knapsack problem features it, too: To compute the maximum value that the knapsack can contain, you compute the value when you include the current item and when you don’t include the current item, and then you take the larger of the two.

MIT professor Erik Demaine has said that an essential part of dynamic programming is guessing. In his opinion, dynamic programming is “careful brute force”. If you don’t know the solution to some problem, then try every possible solution and take a best one. And that is what is going on in these procedures that solve the discrete knapsack problem, the maximum independent set problem, and the coin change problem. The technique that all of these procedures deploy is just a clever way to partition the set of all possible solutions. So, any solution to the coin change problem either includes the first denomination in the list of denominations or it doesn’t include it, and these are the only two possibilities. So, to find the total number of ways to make change for a given amount of money, we just have to process both of these possibilities and combine the results.

Advertisements

The Principle of Mathematical Induction

Let’s say that you are looking at a line of dominoes. You know that if you knock over one domino, the next domino will be knocked over, too. Now you knock over the first domino. What happens?

All of the dominoes are knocked over.

That might seem trivial, but it’s not. Amazingly, this falling-dominoes principle applies to the natural numbers, and you can use it for all sorts of things.

The principle that the dominoes obey is an example of the principle of mathematical induction, which says:

Assume that, if a property P(n) is true for a natural number n, then P(n + 1) is true, too. Also assume that P(n_0) is true for some natural number n_0. Then P is true for all natural numbers greater than or equal to n_0.

So, for example, let P(n) equal “The nth domino is knocked over”. We know that, for all dominoes in our line of dominoes, if P(n) is true, then P(n + 1) is true, because if the nth domino is knocked over, then the (n + 1)th domino is also knocked over.

Now let P(n_0) be true, where n_0 corresponds to the first domino in line. What happens?

All of the dominoes are knocked over.

As you can tell from this example, you can extend the principle of mathematical induction to domains beyond the set of natural numbers. But it can also do more than tell you something obvious about dominoes. In a future post, I will show how you can use the principle to design iterative algorithms.

Miscellaneous Implementations

Over the past year, I have implemented several algorithms and data structures. I decided to do a brief round-up:

I implemented insertion sort for lists of numbers in Python.

I implemented insertion sort for linked lists in Python.

I implemented insertion sort for linked lists in Java.

I implemented prime factorization in Java.

I implemented binary search in Python.

I implemented tries in Python.

Q-Learning

In reinforcement learning, an agent takes actions within an environment. When an agent acts, a reward function assigns feedback to the agent that either positively or negatively reinforces the agent’s action. The agent’s goal is to use this feedback to learn an optimal policy.

For any given state of the environment, a policy tells the agent an action to take when the environment is in that state. An optimal policy tells the agent the best action to take. Of course, there are several different ways to define what a best action is. So, let’s say that an optimal policy maximizes the sum of discounted rewards over time.

Say that Q(s, a) is the reward received from taking action a from state s, plus the discounted value of following the optimal policy thereafter. So, if the agent knows Q, then it can execute the optimal policy. Whenever the agent is in state s, the optimal policy is to take the action a that maximizes Q(s, a). So, the agent’s task is to learn Q.

To learn Q, create a table Q[s][a] and initialize the entries to zero. Then, over and over again, have the agent take actions from states and receive the ensuing rewards. Update Q[s][a] each time. Q[s][a] will converge to the true value of Q as the number of times that each state-action pair is visited converges to infinity.

I implemented Q-learning, and I applied it to a simple environment. The code is up at my GitHub.

References:

Mitchell, Tom. Machine Learning. McGraw-Hill, 1997.

Quines

A quine is a computer program that prints its own source code. Writing a quine is not as easy as you might think.

To learn how to write quines, I made use of David Madore’s discussion of quines and Introduction to the Theory of Computation, by Michael Sipser. However, I prefer Sipser’s discussion. I found it to be a lot clearer than Madore’s.

Sipser does not talk about computer programs. Instead, he talks about Turing machines. A computer program corresponds to a Turing machine. So, a quine corresponds to a Turing machine that outputs a description of itself.

Let QUINE be a Turing machine that outputs a description of itself. QUINE has two parts, C and D, each of which is itself a Turing machine. C outputs a description of D, and D outputs a description of C. So, QUINE outputs a description of its entire self.

D runs first. D outputs onto its tape a description of C. Refer to that description of C as <C>.

Let q(w) be the description of a Turing machine that outputs w. q(w) is a computable function. In fact, given any string w, it is easy to construct a Turing machine P_{w} that outputs w. On any input, P_{w} simply outputs w onto its tape, ignoring the input.

Now, C reads <C> off D’s tape. Then C computes q(<C>). So, now C has the description of a Turing machine that outputs <C>. But that’s D! So, now C can output a description of D.

So, a quine has two parts, the code and the data. The data represents the code. The code uses the data to print the code and the data.

I wrote a quine in C and a quine in Python. To verify that the C program is a quine, type the following commands at the terminal:

gcc -o quine quine.c
diff <(./quine) quine.c

To verify that the Python program is a quine, type the following command:

diff <(python quine.py) quine.py

You will find in both cases that diff produces no output, which means that there are no differences between the programs' outputs and their source code.

Turing Machines

In a previous post, I gave an informal explanation of the P=NP? problem. In that post, I described both deterministic and nondeterministic Turing machines. A couple of months ago, I decided to implement the deterministic Turing machine in Python.

I also implemented a special deterministic Turing machine that decides whether a given positive integer is divisible by 4, just like the hypothetical Turing machine that I describe in my previous post.

I include a Bash script that tests that implementation. The script inputs every multiple of 4, ranging from 4 to 40, into the Turing machine program. The program passes every test.