Counting Counting change

That is not a typo! Let me explain…

I picked up SICP where I left it a few months back in §1.2 which deals with different behavioural patterns of processes generated by procedures (or functions). A very familiar such pattern of computation is tree recursion. Consider the following problem which exhibits this pattern in its solution.

Q. How many different ways can we make change of $100.00, given half-dollars, quarters,
dimes, nickels, and pennies?

A recursive solution should be easily apparent. The number of ways to change amount a using n kinds of coins equals

• the number of ways to change amount a using all but the first kind of coin, plus
• the number of ways to change amount a − d using all n kinds of coins, where d is the denomination of the first kind of coin.

This can be expressed in Scheme. (Here’s a quick tutorial from my previous blog

(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))
                      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)))

SICP now asks us some questions about this procedure as seen below.

Exercise 1.14 (SICP; page 56)

The title of this blog owes itself to the second sub-question which asks us to find the number of steps of computation required to finish a single call to the count-change procedure. We will be counting the number of steps taken to count change 😎.

Let’s look at (a part of) the tree generated by (cc 11 5).

(cc 11 5)  -- (cc -39 5)
    | 
(cc 11 4)  -- (cc -14 4)
    |                  __ (cc -9 3) ...
    |                 /
(cc 11 3)  -- (cc 1 3)
    |                 \__ (cc 1 2) ...
    |                  ______ (cc 1 2) ...
    |                 /
(cc 11 2)  -- (cc 6 2)
    |                 \______ (cc 6 1) ...
    |                   ________ (cc 9 1) ...
    |                  /
(cc 11 1)  -- (cc 10 1)
    |                  \________ (cc 10 0)
(cc 11 0)

Observe the horizontal paths generated by each node of the form (cc 11 n). We can generally say that an amount a from each (cc a n) is repeatedly subtracted using the denomination d(n) until $a−k×d(n) \leq 0$ for some $k$, or creates (cc a n-1).

Drawing the tree for the general case (cc a n) for amount a, number of denominations n and a denomation function d(n), we get

a,n    --    a-d(n),n    --    a−2×d(n),n    --     a−k×d(n),n   --   a−(k+1)×d(n),n
 |              |                  |                    |
 |              |                  |                    |                                 
a,n−1       a−d(n),n−1        a−2×d(n),n−1         a−k×d(n),n−1

where $a − k × d(n) > 0$ and $a − (k + 1) × d(n) ≤ 0$. From these, $k = ⌈a/d(n)⌉ − 1$.

Using this tree, we are now better situated to answer Ex. 1.14. Let us define the following resource usage notation for the count-change procedure with input amount a and pre-set denominations n.

• $R_s(a,n)$ measures the memory space required by the process
• $R_t(a,n)$ measures the number of computation steps to complete the process

The space required by the count-change procedure is simply the height of this tree and grows as $Θ(a)$ with a. The longest path is made by using only pennies.

$R_s(a, n) = Θ(a)$ ✅

The number of steps required to complete a single call to count-change is the number of internal vertices of the general tree we just drew. Let’s break it down.

First, we have the termination case where n is 0. This counts as a single computation step.

For an amount a, number of denominations n and a denomation map d(n):

• we process the (cc a n) node,
• there is at most $⌈a/d(n)⌉$ times you can subtract a denomination from it before it reaches a negative value or zero,
• there are $⌈a/d(n)⌉ - 1$ subtrees for each denomination d(i) where i=0...n.

Therefore, we can write,

\(R_t(a, 0) = 1\)
\(R_t(a, n) = 1 + ⌈a/d(n)⌉ + Σ_{i = 0}^{⌈a/d(n)⌉ − 1} R_t(a − i × d(n), n − 1)\)

Note that there are $⌈a/d(n)⌉ − 1 = Θ(a)$ steps of creating subtrees with denomination n-1. The process of creating a subtree for n=0 is $Θ(1)$, which gives us $Θ(a)$ growth for $R_t(a, 1)$. This is intuitively true because there are $⌈a/1⌉$ repeated subtractions in such a single-chain subtree. These nodes have corresponding termination nodes attached of the form (cc a 0). In total, we have

$R_t(a, 1) = 2⌈a/1⌉ + 1 = Θ(a)$

From this, it’s easy to conclude that the steps required for count-change grows as

$R_t(a, n) = Θ(a^n)$ ✅