sicp-ex-1.14


WARNING: one reader found this analysis to be highly inaccurate.

Solution to Exercise 1.14. Draw the tree illustrating the process generated by the count-change procedure of section 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?

The tree illustration can be as given below. The order of value of coins have been reversed inorder to reduce the size of the diagram. As said in the section 1.2.2, order of coins does not matter. So the resultant procedure will be as given below.

  
 (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) 50) 
         ((= kinds-of-coins 2) 25) 
         ((= kinds-of-coins 3) 10) 
         ((= kinds-of-coins 4) 5) 
         ((= kinds-of-coins 5) 1))) 
                                 11 => 50 25 10 5 1
                                       4|0
                             +----------+---------+
                             |                    |
                        11 => 25 10 5 1      -39 => 50 25 10 5 1
                            4|0
                    +--------+-------+
                    |                |
               11 => 10 5 1    -14 => 25 10 5 1
                   3|1
            +-------+--------------------------------------+
            |                                              |
      11 => 5 1                                       1=> 10 5 1
           1|2                                            1|0
    +-------+-------+                                 +----+---------+
    |               |                                 |              |
 11=> 1          6 => 5 1                           1=> 5 1      -9 => 10 5 1
                   1|1                               1|0
           +--------+----+                      +-----+---+
           |             |                      |         |
        6 => 1        1 => 5 1               1 => 1     -4=> 5 1
                        1|0
                    +----+----+
                    |         |
                1 => 1     -4=> 5 1

The exercise also asks for the orders of growth in space and time, as the amount increases. (Forgive any errors or imprecision in my answer, as my analysis skills are still very basic.)

Space required (maximum height of the call tree) grows linearly with the amount, as it is determined by the number of times the smallest denomination divides into the amount. i.e. O(a)

Time required (number of operations) grows in relation to O(a^n). i.e. O(a * a * a * ...) since the 2nd branch is O(a), and the first branch is called O(n) times.

I made a pretty svg version of the call tree for 11 cents, generated by a slightly modified version of the function writing a Graphviz description.

qu1j0t3

I think space is O(n^2) as this is not a tail recursive function.


Another more formal approach:

count-change space order of growth:

count-change time order of growth:

  1. cc(n, 1) = O(n)
  2. cc(n, 2) = cc(n, 1) + cc(n-5, 2)
  3. each 2. step is O(n) and there are roughly n/5 such steps
  4. so we have O(n^2)
  5. by analogue we get O(n^k) (k currencies) for cc(n, k)

Feel free to expand if needed.

gollum0


Another wonderful explanation


<< Previous exercise (1.13) | sicp-solutions | Next exercise (1.15) >>