SICP Exercise 1.14: orders of growth of count-change
2021-09-28
Categories: Programming
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 count-change
procedure:
1(trace-define (count-change amount) 2 (cc amount 5)) 3 4(trace-define (cc amount kinds-of-coins) 5 (cond ((= amount 0) 1) 6 ((or (< amount 0) (= kinds-of-coins 0)) 0) 7 (else (+ (cc amount 8 (- kinds-of-coins 1)) 9 (cc (- amount 10 (first-denomination kinds-of-coins)) 11 kinds-of-coins))))) 12 13(define (first-denomination kinds-of-coins) 14 (cond ((= kinds-of-coins 1) 1) 15 ((= kinds-of-coins 2) 5) 16 ((= kinds-of-coins 3) 10) 17 ((= kinds-of-coins 4) 25) 18 ((= kinds-of-coins 5) 50)))
In making changes for 11 cents, this procedure can be illustrated by a tree:
1 (11, 5) 2 _______|_______ 3 | | 4 (11, 4) (-39, 5) 5 _______|_______ | 6 | | | 7 (11, 3) (-14, 4) 0 8 ____________|____________ | 9 | | | 10 (11, 2) (1, 3) 0 11 ______|______ _____|_____ 12 | | | | 13 (11, 1) (6, 2) (1, 2) (-9, 3) 14 __|__ __|__ __|__ | 15 | | | | | | | 16 (11, 0) (10, 1) (6, 1) (1, 2) (1, 1) (-4, 2) 0 17 | | | __|__ |__ | 18 | | | | | | | 19 0 (9, 1) 1 (1, 1) (-4, 2) 1 0 20 | | | 21 | | | 22 1 1 0
Verify by running the above procedure in debug mode:
1$ racket 1.14-count-change.rkt 11 2>(count-change 11) 3>(cc 11 5) 4> (cc 11 4) 5> >(cc 11 3) 6> > (cc 11 2) 7> > >(cc 11 1) 8> > > (cc 11 0) 9< < < 0 10> > > (cc 10 1) 11> > > >(cc 10 0) 12< < < <0 13> > > >(cc 9 1) 14> > > > (cc 9 0) 15< < < < 0 16> > > > (cc 8 1) 17> > > > >(cc 8 0) 18< < < < <0 19> > > > >(cc 7 1) 20> > > > > (cc 7 0) 21< < < < < 0 22> > > > > (cc 6 1) 23> > > >[10] (cc 6 0) 24< < < <[10] 0 25> > > >[10] (cc 5 1) 26> > > >[11] (cc 5 0) 27< < < <[11] 0 28> > > >[11] (cc 4 1) 29> > > >[12] (cc 4 0) 30< < < <[12] 0 31> > > >[12] (cc 3 1) 32> > > >[13] (cc 3 0) 33< < < <[13] 0 34> > > >[13] (cc 2 1) 35> > > >[14] (cc 2 0) 36< < < <[14] 0 37> > > >[14] (cc 1 1) 38> > > >[15] (cc 1 0) 39< < < <[15] 0 40> > > >[15] (cc 0 1) 41< < < <[15] 1 42< < < <[14] 1 43< < < <[13] 1 44< < < <[12] 1 45< < < <[11] 1 46< < < <[10] 1 47< < < < < 1 48< < < < <1 49< < < < 1 50< < < <1 51< < < 1 52< < <1 53> > >(cc 6 2) 54> > > (cc 6 1) 55> > > >(cc 6 0) 56< < < <0 57> > > >(cc 5 1) 58> > > > (cc 5 0) 59< < < < 0 60> > > > (cc 4 1) 61> > > > >(cc 4 0) 62< < < < <0 63> > > > >(cc 3 1) 64> > > > > (cc 3 0) 65< < < < < 0 66> > > > > (cc 2 1) 67> > > >[10] (cc 2 0) 68< < < <[10] 0 69> > > >[10] (cc 1 1) 70> > > >[11] (cc 1 0) 71< < < <[11] 0 72> > > >[11] (cc 0 1) 73< < < <[11] 1 74< < < <[10] 1 75< < < < < 1 76< < < < <1 77< < < < 1 78< < < <1 79< < < 1 80> > > (cc 1 2) 81> > > >(cc 1 1) 82> > > > (cc 1 0) 83< < < < 0 84> > > > (cc 0 1) 85< < < < 1 86< < < <1 87> > > >(cc -4 2) 88< < < <0 89< < < 1 90< < <2 91< < 3 92> > (cc 1 3) 93> > >(cc 1 2) 94> > > (cc 1 1) 95> > > >(cc 1 0) 96< < < <0 97> > > >(cc 0 1) 98< < < <1 99< < < 1 100> > > (cc -4 2) 101< < < 0 102< < <1 103> > >(cc -9 3) 104< < <0 105< < 1 106< <4 107> >(cc -14 4) 108< <0 109< 4 110> (cc -39 5) 111< 0 112<4 1134
Orders of growth
From section 1.2.2:
In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.
Space
The maximum depth of the tree will always be the branch that represents the case of all pennies (cc n 1
):
1> > >(cc 11 1) 2> > > (cc 11 0) 3< < < 0 4> > > (cc 10 1) 5> > > >(cc 10 0) 6< < < <0 7> > > >(cc 9 1) 8> > > > (cc 9 0) 9< < < < 0 10> > > > (cc 8 1) 11> > > > >(cc 8 0) 12< < < < <0 13> > > > >(cc 7 1) 14> > > > > (cc 7 0) 15< < < < < 0 16> > > > > (cc 6 1) 17> > > >[10] (cc 6 0) 18< < < <[10] 0 19> > > >[10] (cc 5 1) 20> > > >[11] (cc 5 0) 21< < < <[11] 0 22> > > >[11] (cc 4 1) 23> > > >[12] (cc 4 0) 24< < < <[12] 0 25> > > >[12] (cc 3 1) 26> > > >[13] (cc 3 0) 27< < < <[13] 0 28> > > >[13] (cc 2 1) 29> > > >[14] (cc 2 0) 30< < < <[14] 0 31> > > >[14] (cc 1 1) 32> > > >[15] (cc 1 0) 33< < < <[15] 0 34> > > >[15] (cc 0 1) 35< < < <[15] 1 36< < < <[14] 1 37< < < <[13] 1 38< < < <[12] 1 39< < < <[11] 1 40< < < <[10] 1 41< < < < < 1 42< < < < <1 43< < < < 1 44< < < <1 45< < < 1 46< < <1
So, the orders of growth of the space will be O(n)
.
Number of steps
I cannot solve this part. So I googled for the solution and this one helped me understand how to calculate time complexity of this procedure. I will note it down for the future reference.
Look at the code:
1 (cond ((= amount 0) 1) 2 ((or (< amount 0) (= kinds-of-coins 0)) 0) 3 (else (+ (cc amount 4 (- kinds-of-coins 1)) 5 (cc (- amount 6 (first-denomination kinds-of-coins)) 7 kinds-of-coins)))))
(cond ((= amount 0) 1)
performs only one operation O(1)
. If using only pennies, then:
1T(n, 1) = 1 + T(n, 0) + T(n-1, 1) 2T(n, 1) = 1 + 1 + T(n-1, 1) 3 4T(n - (n-1), 1) = 1 + 1 + T(0, 1) = 1 + 1 + 1 = 3 5T(n - (n-2), 1) = 1 + 1 + T(n - (n-1), 1) = 1 + 1 + 3 = 5 6T(n - (n-3), 1) = 1 + 1 + T(n - (n-2), 1) = 1 + 1 + 5 = 7 7T(n - (n-4), 1) = 1 + 1 + T(n - (n-3), 1) = 1 + 1 + 7 = 9 8... 9 10T(n, 1) = 2n + 1
Verify this by running (cc 11 1)
in debug mode and counting the number of calls of cc
:
1$ racket 1.14-count-change.rkt 11 2>(count-change 11) 3>(cc 11 1) 4> (cc 11 0) 5< 0 6> (cc 10 1) 7> >(cc 10 0) 8< <0 9> >(cc 9 1) 10> > (cc 9 0) 11< < 0 12> > (cc 8 1) 13> > >(cc 8 0) 14< < <0 15> > >(cc 7 1) 16> > > (cc 7 0) 17< < < 0 18> > > (cc 6 1) 19> > > >(cc 6 0) 20< < < <0 21> > > >(cc 5 1) 22> > > > (cc 5 0) 23< < < < 0 24> > > > (cc 4 1) 25> > > > >(cc 4 0) 26< < < < <0 27> > > > >(cc 3 1) 28> > > > > (cc 3 0) 29< < < < < 0 30> > > > > (cc 2 1) 31> > > >[10] (cc 2 0) 32< < < <[10] 0 33> > > >[10] (cc 1 1) 34> > > >[11] (cc 1 0) 35< < < <[11] 0 36> > > >[11] (cc 0 1) 37< < < <[11] 1 38< < < <[10] 1 39< < < < < 1 40< < < < <1 41< < < < 1 42< < < <1 43< < < 1 44< < <1 45< < 1 46< <1 47< 1 48<1 491 50 51$ for amount in (seq 1 11); echo -n "T($amount, 1): "; racket 1.14-count-change.rkt $amount | grep -c 'cc'; end 52T(1, 1): 3 53T(2, 1): 5 54T(3, 1): 7 55T(4, 1): 9 56T(5, 1): 11 57T(6, 1): 13 58T(7, 1): 15 59T(8, 1): 17 60T(9, 1): 19 61T(10, 1): 21 62T(11, 1): 23
Let’s go one step further with 2 kind of coins:
1T(n, 2) = 1 + T(n, 1) + T(n-5, 2) 2T(n, 1) = 2n + 1 3T(n-5, 2) = 1 + T(n-5, 1) + T(n-10, 2) = 1 + (2n + 1) + T(n-10, 2) 4T(n-10, 2) = 1 + (2n + 1) + (2n + 1) + T(n-15, 2) 5... 6 7T(n, 2) = (n/5) * 2n + 1
When k = 3:
1T(n, 3) = 1 + T(n, 2) + T(n-10, 3) 2T(n, 2) = (n/5) * 2n + 1 3T(n-10, 3) = 1 + T(n-10, 2) + T(n-20, 3) = 1 + ((n/5) * 2n + 1) + T(n-20, 3) 4... 5 6T(n, 3) = (n/10) * ((n/5) * 2n + 1)
k = 4:
1T(n, 4) = (n/25) * T(n, 3)
k = 5:
1T(n, 5) = (n/50) * T(n, 4)
So, the time complexity of the count-change
procedure with 5 kinds of coins is: O(n5).
Related Posts:
- SICP Exercise 2.77: expected a procedure that can be applied to arguments, given #f
- SICP Exercise 2.43: Eight queens: interchange the order of the nested mappings
- SICP Exercise 2.42: Eight queens puzzle
- SICP Exercise 2.41: Triple sum
- SICP Exercise 2.35: Counting leaves of a tree