Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.14

From Drewiki
Jump to: navigation, search

Problem

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?

Solution

Here's a version of count-change which counts the number of times it is called. This count is useful for validating our answer to the exercise.

(define count 0)
 
(define (count-change amount)
  (set! count 0)
  (cc amount 5))
 
(define (cc amount kinds-of-coins)
  (let ()
    (set! count (+ 1 count))
    (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)))

The count for (count-change 11) is 55. The graph for this evaluation isn't shown here, but if you draw it on paper, you can see that it generates a tree recursive process.

Each time procedure cc is called, it returns 1, 0 or the sum of two subtrees. Let's say, then, that each invocation of cc, that is, each node in the evaluation tree, performs one operation.

For amount n and kinds-of-coins 5, the number of operations performed by procedure cc is 1 plus the number of operations performed by the subtree generated by (cc n 4), plus the number of operations performed by the subtree generated by (cc (- n 50) 5). Let's use N(n,m) to denote the number of operations performed by a subtree (cc n m). Then we have:

N(n,5) = 1 + N(n,4) + N(n − 50,5)

Let's expand the first N term by repeating this process for (cc n 4):

N(n,4) = 1 + N(n,3) + N(n − 25,4)

Keep expanding the first N term of each subtree:

N(n,3) = 1 + N(n,2) + N(n − 10,3)

N(n,2) = 1 + N(n,1) + N(n − 5,2)

N(n,1) = 1 + N(n,0) + N(n − 1,1)

(cc n 0) is a termination case: it performs only a single operation (returns 0):

N(n,0) = 1

N(n,1) = 1 + 1 + N(n − 1,1)

Let's now consider the other subtree of (cc n 1), (cc (- n 1) 1):

N(n − 1,1) = 1 + N(n − 1,0) + N(n − 2,1)

Once again, (cc (- n 1) 0) is a termination case and performs only a single operation. This process continues until the amount argument of cc is (- n n), at which point we've fully evaluated the (cc n 1) subtree:

N(nn,1) = 1

Working our way back up:

N(n − (n − 1),1) = 1 + 1 + 1 = 3

N(n − (n − 2),1) = 1 + 1 + N(n − (n − 1),1) = 1 + 1 + 3 = 5

N(n − (n − 3),1) = 1 + 1 + N(n − (n − 2),1) = 1 + 1 + 5 = 7

N(n − (n − 4),1) = 1 + 1 + N(n − (n − 3),1) = 1 + 1 + 7 = 9

It's easy to see that this process continues until we're back to (cc n 1):

N(n,1) = 1 + 1 + N(n − 1,1) = 2n + 1

We can verify this by drawing the graph for (cc 11 1) and counting the number of nodes. Note that the amount of storage required for an applicative-order evaluation of the (cc n 1) subtree is also proportional to 2n + 1, since the + operations are deferred until the value of each subtree is calculated.

When we're dealing with θ-notation orders of growth, we can ignore constant factors, so it's sufficient to say that evaluating (cc n 1) requires order n number of steps and order n storage, since 2n + 1 is linear in n. Dropping these constant terms makes it easier to calculate orders of growth for the other terms in the process tree.

(count-change n) generates a tree-recursive process. We know from the text that tree-recursive processes require space proportional to the depth of the tree, and we know that (cc n 1) generates the deepest subtree of the process (since other subtrees reduce the size of n), so we can say at this point that count-change requires space of order n (i.e., linear).

We also know from the text that tree-recursive processes require a number of operations proportional to the number of nodes in the tree, so we have to count the remaining number of operations before we can answer the second part of the question, i.e., count-change's order of growth of operations.

Let's go back to the root of the subtree which generated (cc n 1):

N(n,2) = 1 + N(n,1) + N(n − 5,2)

We know the value of the first N term. The 2nd N term is:

N(n − 5,2) = 1 + N(n − 5,1) + N(n − 10,2)

This expansion continues until n is <= 0, or roughly n/5 times, since each expansion of the 2nd term subtracts 5 from its amount argument. Each one of these expansions produces an N(a 1) term, where a is the amount, and each of those terms produces 2a + 1 operations. Subtracting a constant from n at each step doesn't change the fact that each step is a linear (order n) process, so we can ignore the subtraction when calculating the order of growth. n times n/5 steps is n2 / 5 steps. This term overwhelms the 2n + 1 steps we calculated for the previous branch, so we can ignore the 2n + 1 term now and say that calculating (cc n 2) has order n2 / 5 steps.

Now we consider the next node up the tree, the one which generated (cc n 2):

N(n,3) = 1 + N(n,2) + N(n − 10,3)

The analysis for this step is similar to the one we performed for N(n,2): calculating (cc (- n 10) 3) produces roughly n/10 more nodes, each of which evaluates (cc x 2). We know that evaluating (cc x 2) is order x2 / 5, so (cc n 3) is roughly n/10 times that, n3 / 50. Again, the n3 term dominates the growth of the process, so we can ignore the lesser orders of growth of the other nodes we've considered and say that (cc n 3) has order n3 / 50 growth.

Calculating N(n,4) and N(n,5) follows similar logic. It's then straightforward to show that the number of steps required to evaluate (cc n 5) is θ(n5).

Personal tools