SICP - Solution: Exercise 1.14

SICP - Solution: Exercise 1.14

October 9, 2018

Exercise 1.14 #

Draw the tree illustrating the process generated by the count-change procedure of 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

Solution #

By updating the call with display, it is possible to generate data in GrapViz DOT format and plot it. The call that match (= amount 0) are in darker grey.

digraph G {
node [color = gray95,style=filled];
graph [ranksep=0.25];
node [color = gray95,style=filled,fontsize=9,shape=box, margin=.08, width=0, height=0 ];
edge [penwidth=.5, arrowsize=0.5];
"[0] (cc 11 5)" [label="(cc 11 5)", ];
"[0] (cc 11 5)" -> "[1] (cc 11 4)"; "[1] (cc 11 4)" [label="(cc 11 4)", ];
"[1] (cc 11 4)" -> "[2] (cc 11 3)"; "[2] (cc 11 3)" [label="(cc 11 3)", ];
"[2] (cc 11 3)" -> "[3] (cc 11 2)"; "[3] (cc 11 2)" [label="(cc 11 2)", ];
"[3] (cc 11 2)" -> "[4] (cc 11 1)"; "[4] (cc 11 1)" [label="(cc 11 1)", ];
"[4] (cc 11 1)" -> "[5] (cc 11 0)"; "[5] (cc 11 0)" [label="(cc 11 0)", ];
"[4] (cc 11 1)" -> "[5] (cc 10 1)"; "[5] (cc 10 1)" [label="(cc 10 1)", ];
"[5] (cc 10 1)" -> "[6] (cc 10 0)"; "[6] (cc 10 0)" [label="(cc 10 0)", ];
"[5] (cc 10 1)" -> "[6] (cc 9 1)"; "[6] (cc 9 1)" [label="(cc 9 1)", ];
"[6] (cc 9 1)" -> "[7] (cc 9 0)"; "[7] (cc 9 0)" [label="(cc 9 0)", ];
"[6] (cc 9 1)" -> "[7] (cc 8 1)"; "[7] (cc 8 1)" [label="(cc 8 1)", ];
"[7] (cc 8 1)" -> "[8] (cc 8 0)"; "[8] (cc 8 0)" [label="(cc 8 0)", ];
"[7] (cc 8 1)" -> "[8] (cc 7 1)"; "[8] (cc 7 1)" [label="(cc 7 1)", ];
"[8] (cc 7 1)" -> "[9] (cc 7 0)"; "[9] (cc 7 0)" [label="(cc 7 0)", ];
"[8] (cc 7 1)" -> "[9] (cc 6 1)"; "[9] (cc 6 1)" [label="(cc 6 1)", ];
"[9] (cc 6 1)" -> "[10] (cc 6 0)"; "[10] (cc 6 0)" [label="(cc 6 0)", ];
"[9] (cc 6 1)" -> "[10] (cc 5 1)"; "[10] (cc 5 1)" [label="(cc 5 1)", ];
"[10] (cc 5 1)" -> "[11] (cc 5 0)"; "[11] (cc 5 0)" [label="(cc 5 0)", ];
"[10] (cc 5 1)" -> "[11] (cc 4 1)"; "[11] (cc 4 1)" [label="(cc 4 1)", ];
"[11] (cc 4 1)" -> "[12] (cc 4 0)"; "[12] (cc 4 0)" [label="(cc 4 0)", ];
"[11] (cc 4 1)" -> "[12] (cc 3 1)"; "[12] (cc 3 1)" [label="(cc 3 1)", ];
"[12] (cc 3 1)" -> "[13] (cc 3 0)"; "[13] (cc 3 0)" [label="(cc 3 0)", ];
"[12] (cc 3 1)" -> "[13] (cc 2 1)"; "[13] (cc 2 1)" [label="(cc 2 1)", ];
"[13] (cc 2 1)" -> "[14] (cc 2 0)"; "[14] (cc 2 0)" [label="(cc 2 0)", ];
"[13] (cc 2 1)" -> "[14] (cc 1 1)"; "[14] (cc 1 1)" [label="(cc 1 1)", ];
"[14] (cc 1 1)" -> "[15] (cc 1 0)"; "[15] (cc 1 0)" [label="(cc 1 0)", ];
"[14] (cc 1 1)" -> "[15] (cc 0 1)"; "[15] (cc 0 1)" [label="(cc 0 1)",color=gray80];
"[3] (cc 11 2)" -> "[4] (cc 6 2)"; "[4] (cc 6 2)" [label="(cc 6 2)", ];
"[4] (cc 6 2)" -> "[5] (cc 6 1)"; "[5] (cc 6 1)" [label="(cc 6 1)", ];
"[5] (cc 6 1)" -> "[6] (cc 6 0)"; "[6] (cc 6 0)" [label="(cc 6 0)", ];
"[5] (cc 6 1)" -> "[6] (cc 5 1)"; "[6] (cc 5 1)" [label="(cc 5 1)", ];
"[6] (cc 5 1)" -> "[7] (cc 5 0)"; "[7] (cc 5 0)" [label="(cc 5 0)", ];
"[6] (cc 5 1)" -> "[7] (cc 4 1)"; "[7] (cc 4 1)" [label="(cc 4 1)", ];
"[7] (cc 4 1)" -> "[8] (cc 4 0)"; "[8] (cc 4 0)" [label="(cc 4 0)", ];
"[7] (cc 4 1)" -> "[8] (cc 3 1)"; "[8] (cc 3 1)" [label="(cc 3 1)", ];
"[8] (cc 3 1)" -> "[9] (cc 3 0)"; "[9] (cc 3 0)" [label="(cc 3 0)", ];
"[8] (cc 3 1)" -> "[9] (cc 2 1)"; "[9] (cc 2 1)" [label="(cc 2 1)", ];
"[9] (cc 2 1)" -> "[10] (cc 2 0)"; "[10] (cc 2 0)" [label="(cc 2 0)", ];
"[9] (cc 2 1)" -> "[10] (cc 1 1)"; "[10] (cc 1 1)" [label="(cc 1 1)", ];
"[10] (cc 1 1)" -> "[11] (cc 1 0)"; "[11] (cc 1 0)" [label="(cc 1 0)", ];
"[10] (cc 1 1)" -> "[11] (cc 0 1)"; "[11] (cc 0 1)" [label="(cc 0 1)",color=gray80];
"[4] (cc 6 2)" -> "[5] (cc 1 2)"; "[5] (cc 1 2)" [label="(cc 1 2)", ];
"[5] (cc 1 2)" -> "[6] (cc 1 1)"; "[6] (cc 1 1)" [label="(cc 1 1)", ];
"[6] (cc 1 1)" -> "[7] (cc 1 0)"; "[7] (cc 1 0)" [label="(cc 1 0)", ];
"[6] (cc 1 1)" -> "[7] (cc 0 1)"; "[7] (cc 0 1)" [label="(cc 0 1)",color=gray80];
"[5] (cc 1 2)" -> "[6] (cc -4 2)"; "[6] (cc -4 2)" [label="(cc -4 2)", ];
"[2] (cc 11 3)" -> "[3] (cc 1 3)"; "[3] (cc 1 3)" [label="(cc 1 3)", ];
"[3] (cc 1 3)" -> "[4] (cc 1 2)"; "[4] (cc 1 2)" [label="(cc 1 2)", ];
"[4] (cc 1 2)" -> "[5] (cc 1 1)"; "[5] (cc 1 1)" [label="(cc 1 1)", ];
"[5] (cc 1 1)" -> "[6] (cc 1 0)"; "[6] (cc 1 0)" [label="(cc 1 0)", ];
"[5] (cc 1 1)" -> "[6] (cc 0 1)"; "[6] (cc 0 1)" [label="(cc 0 1)",color=gray80];
"[4] (cc 1 2)" -> "[5] (cc -4 2)"; "[5] (cc -4 2)" [label="(cc -4 2)", ];
"[3] (cc 1 3)" -> "[4] (cc -9 3)"; "[4] (cc -9 3)" [label="(cc -9 3)", ];
"[1] (cc 11 4)" -> "[2] (cc -14 4)"; "[2] (cc -14 4)" [label="(cc -14 4)", ];
"[0] (cc 11 5)" -> "[1] (cc -39 5)"; "[1] (cc -39 5)" [label="(cc -39 5)", ];
}

Orders of growth of space #

Since this is a recursive process, the orders of growth of the space will be proportional to the depth of the calls.

It is easy to see that the longest series of calls will be when making the change of the amount n using only pennies. The order of growth of space for cc will be $\mathrm\Theta(n)$

Orders of growth of the number of steps #

For estimating the orders of growth of number of steps, we will focus on counting the number of call to cc.

The solution presented here is directly insprired from this blog post by Bill the Lizard.

The first step is to get an intuitive understanding of the shape of the growth by exploring low dimension solutions that we can plot. Let’s start with graphing the shape of the trees when using only pennies by charting the tree for (cc 6 1).

digraph G {
node [color = gray95,style=filled];
graph [ranksep=0.3,size=7];
node [color = gray95,style=filled,fontsize=9,shape=box, margin=.08, width=0, height=0 ];
edge [penwidth=.1, arrowsize=0.5];
"[0] (cc 6 1)" [label="(cc 6 1)",color=lightblue];
"[0] (cc 6 1)" -> "[1] (cc 6 0)"; "[1] (cc 6 0)" [label="(cc 6 0)", ];
"[0] (cc 6 1)" -> "[1] (cc 5 1)"; "[1] (cc 5 1)" [label="(cc 5 1)",color=lightblue];
"[1] (cc 5 1)" -> "[2] (cc 5 0)"; "[2] (cc 5 0)" [label="(cc 5 0)", ];
"[1] (cc 5 1)" -> "[2] (cc 4 1)"; "[2] (cc 4 1)" [label="(cc 4 1)",color=lightblue];
"[2] (cc 4 1)" -> "[3] (cc 4 0)"; "[3] (cc 4 0)" [label="(cc 4 0)", ];
"[2] (cc 4 1)" -> "[3] (cc 3 1)"; "[3] (cc 3 1)" [label="(cc 3 1)",color=lightblue];
"[3] (cc 3 1)" -> "[4] (cc 3 0)"; "[4] (cc 3 0)" [label="(cc 3 0)", ];
"[3] (cc 3 1)" -> "[4] (cc 2 1)"; "[4] (cc 2 1)" [label="(cc 2 1)",color=lightblue];
"[4] (cc 2 1)" -> "[5] (cc 2 0)"; "[5] (cc 2 0)" [label="(cc 2 0)", ];
"[4] (cc 2 1)" -> "[5] (cc 1 1)"; "[5] (cc 1 1)" [label="(cc 1 1)",color=lightblue];
"[5] (cc 1 1)" -> "[6] (cc 1 0)"; "[6] (cc 1 0)" [label="(cc 1 0)", ];
"[5] (cc 1 1)" -> "[6] (cc 0 1)"; "[6] (cc 0 1)" [label="(cc 0 1)",color=gray80];
}

Colors in this chart indicate the number of kinds-of-coins.

The process here is linear: every node is splitting into two substep, but only the node with (c x 1) on the right will recurse deeper. All the (c x 0) are leaves of this tree since it indicates that there are no more type of coins to use.

From this we notice that:

  • there are 6 blue nodes from (c 6 1) to (c 1 1)
  • there are 6 grey nodes from (c 6 0) to (c 1 0)
  • there is one dark grey node (c 0 1) with a mount of 0, indicating a solution

If $T(n,m)$ is the number of call to cc for amount $n$ and $m$ type of coin, we can see that:

$$T(6,1)=2\times6+1$$

From there, we can generalize to any amount $m$ using only pennies:

$$T(n,1)=2n+1$$

Let’s go one step further by exploring how things work with two kinds of coins. By drawing the tree for (cc 12 2) and arranging the nodes a little, we see that we have a neat 2 dimensional array:

Example image

Let’s break it down:

  • There are 4 green nodes for (c x 2) corresponding to how many time you can subtract a nickel from 12, plus one.
  • Then for each of the green node, there is the option of using only pennies, which is the case that we looked at first.

For an amount $n$, there is at most $Floor\left(\frac n5\right)+1$ times you can subtract nickels from it before reaching zero or a negative value. By simplifying a little and ignoring the floor that won’t impact a lot the result when the number grows larger, we can split the number of calls to cc and compute $T(n,2)$:

  • there is $\frac n5+1$ green node
  • for each green node, there is a node for pennies that start from the value $n$

We can rewrite this as an equation and simplify it:

$$T(n,2) =\frac n5+1+ \sum_{i=0}^{n/5}T(n-5i,1)$$

$$T(n,2) =\frac n5+1+ \sum_{i=0}^{n/5}(2n-10i+1)$$

$$T(n,2) =\frac n5+1+\frac{2n^2}5+\frac n5-10 \sum_{i=0}^{n/5}i$$

$$T(n,2) =\frac n5+1+\frac{2n^2}5+\frac n5-10\frac{{\displaystyle\frac n5}\left({\displaystyle\frac n5}+1\right)}2$$

$$T(n,2) =\frac{2n}5+\frac{2n^2}5-\frac{n^2}5+n+1$$

Very interestingly, it is possible to define a function that gives the exact number of steps for a given number $n$:

$$T(n,2) =\frac{n^2+7n}5+1$$

Which means that for two type of coins, the orders of growth of number of steps is:

$$T(n,2) =\mathrm\Theta(n^2)$$

For $T(n,3)$:

$$T(n,3) =\frac n{10}+1+ \sum_{i=0}^{n/10}T(n-10i,2)$$

if you take the trouble to expand the equation, you will find that:

$$T(n,3) =\mathrm\Theta(n^3)$$

by continuing to apply the formulas:

$$T(n,3) =\frac n{10}+1+ \sum_{i=0}^{n/10}T(n-10i,1)$$

$$T(n,4) =\frac n{25}+1+ \sum_{i=0}^{n/25}T(n-25i,1)$$

$$T(n,5) =\frac n{50}+1+ \sum_{i=0}^{n/50}T(n-50i,1)$$

By doing all the expansion you find that the orders of growth of number of steps is:

$$T(n,5) =\mathrm\Theta(n^5)$$

Overall, this is not only a very slow process, it is also a very inefficient way to implement this computation, because of all the repetitions. You can have a look at the solution for this exercice by Sarabander here to see how to implement the solution in only $n^2$.

Calendar September 21, 2022
Edit Edit this page