Tuesday, December 22, 2009

SICP Exercise 1.14: Counting change

From SICP section 1.2.3 Orders of Growth

Exercise 1.14 asks us to draw the tree illustrating the process generated by the count-change procedure presented in section 1.2.2 in making change for 11 cents.
(define (count-change amount)
(cc amount 5))

(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))

(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))

Running the code with the specified input shows us how many ways there are to make change for 11 cents with five coins.
> (count-change 11)

A quick scan of the code shows that the cc procedure contains two recursive calls to itself, resulting in the tree-shaped process structure mentioned in the question. Leaf nodes of the tree are reached when the base cases are met, that is when the amount is less than or equal to zero, or when the kinds of coins remaining reaches zero.

When a node splits, its left-hand child is passed the same amount and one fewer kinds of coins. The right-hand child is passed an amount that is reduced by the highest-denomination coin available to its parent node, and the same number of kinds of coins. (Click the images enlarge.)

I've color-coded the nodes of the tree. White nodes are those leaf nodes that evaluate to 0, blue nodes are those leaf nodes that evaluate to 1 and contribute to the final answer. The yellow nodes are those that branch recursively.

Orders of growth

The exercise also asks us to find the orders of growth of the space and number of steps used by the count-change process as the amount to be changed increases. (Note that we are not really concerned with the orders of growth as the number of kinds of coins grows, only the amount to be changed.)

Space - As we saw in the Fibonacci procedure in section 1.2.2, the space required by the count-change procedure grows linearly with the input. The space required is proportional to the maximum depth of the tree. At any point in the computation we only need to keep track of the nodes above the current node.

Since the height of the tree is proportional to the amount to be changed, the order of growth of the space required by the count-change procedure is O(n).

Number of steps - The diagram illustrates that this procedure, much like the recursive procedure for computing Fibonacci numbers that we saw before, in not very efficient. Much of the computation being done is repeated.

If we look closely at a call to cc where kinds-of-coins is equal to one, we can see each call generates two more calls until we reach a terminal node.

If we define the function T(a, k) to be the number of calls to cc generated by calling (cc n k), where n is the amount and k is the number of kinds of coins, then

T(n, 1) = 2n + 1

or in Big-O notation,

T(n, 1) = O(n)

Now let's take a look at a partial graph of a call to (cc 50 2).

There are two interesting things to point out here. First, there are n/5 calls to cc made where k = 2 kinds of coins (look down the right hand side of the diagram above). This is because each call is made with 5 cents less in the amount argument until a terminal node is reached. The second interesting thing is that each of these n/5 calls to (cc n 2) generates an entire (cc n 1) subtree.

That means that

T(n, 2) = (n/5) * 2n + 1

and because of the multiplication of terms

T(n, 2) = O(n2)

Similarly, if we look at the graph of (cc 50 3) we can see n/10 calls to cc where k = 3, each of which generates its own (cc n 2) subtree.

From this we find that

T(n, 3) = O(n3)

Finally, it's easy enough to show that we'll get the same pattern when k = 4 and k = 5. The n/50 nodes generated when k = 5 each generate n/25 nodes with k = 4, each of which generates a node where k = 3.

And so the final answer we arrive at for the time complexity of the count-change procedure with five kinds of coins is

T(n, 5) = O(n5)


For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.


Anonymous said...

Thanks Bill, a very thorough explanation!

Anonymous said...

Gah... I just can't get all of it.
I'm 16. Maybe I'm trying to read this book too soon? Or maybe I'm just not smart enough :/.
Anyway, still a very helpful explanation, thanks.

jairp said...

Brilliant explanation. Really thorough explanation of how you derived your answer.

Your article was easy to follow and the graphics really helped out a lot.

Keep up the good work and I am expecting similar articles on other unsolved exercises.

miles said...

Hi Bill,

Do you think it would have still been possible to arrive at this answer without previous formal training in algorithm analysis? Your explanation has been nothing but helpful, but I don't think there would have been a snowball's chance in hell of me coming up with this on my own. It's a bit discouraging. I get to take Algorithms this Fall, thankfully, so hopefully that will be of help in solving order of growth problems like this. I do have a copy of CLRS for this coming Fall, so maybe it would have something insightful for dealing with these sorts of problems? In any case, thanks for posting a great solution.

Bill the Lizard said...

Hi miles,

I mostly used techniques covered in SICP and in the lectures to answer this question, so it should be possible to solve it, just maybe not in the same level of detail. I did have two algorithms courses in college prior to starting SICP, so those definitely provided a foundation for me to work from.

CLRS was the book we used in one of those courses, so I am familiar with it, including chapters 2 and 3 that cover analysis and Big-O notation. You'll definitely get a lot out of it.

You can also check out some of the answers on Plain English explanation of Big O.

Good luck!

brettshollenberger said...

Hey Bill-
I'm really appreciating your explanations as I work through this book; I'm not finding the same answer as you here, and I'm not sure whether or not you're right. Forgive me, as I'm re-learning Algebra so I can work through this book, and have a total zero previous algorithms courses, but:

It seems to me in the case with 2 coins, the entire 1 coin subtree (2n + 1) is duplicated once, leaving us with 2(2n+1), or 4n + 2. Rather than n/5(2n + 1), it seems we're actually making 4n + 2 + n/5 calls, or still roughly O(n). In the case (50, 2), you have ~210 calls, or 4n + n/5 and some change.

And that seems to be the pattern for each of the additional coins, where the real weight in 5 coins is 10n, which is still linear n.

As a general rule, what I see is that the subtree for a single coin continues to add 2 processes as n increases by one. For each coin, the single n tree is doubled plus n/the value of the coin. This may help you understand what I'm thinking or where I'm going wrong.

Solsk Gaer said...


服部拓也 said...

I am Japanese. This entry is very useful for me. Thank you so much.

Z.Lahcen said...

The order of growth of the space required by the count-change procedure seems O(log(n)).

김홍균 said...

you always help me, thank you.

김홍균 said...

you always help me, thank you.

Anonymous said...

Thank you very much for the amazingly clear explanation! I don't think I would have gotten the answer myself if I tried.

Unknown said...

I don't understand one thing, if the time complexity is n^5 and n=11 why total steps are only 5n(55) rather n^5(161,051)