Solution to SICP Exercise 1.14

(require (lib "19.ss" "srfi"))
(map (lambda (amount)
       (let ((start-time (current-time time-process))
              (change (count-change amount))
              (end-time (current-time time-process)))
         (let ((diff (time-difference end-time start-time)))
           (list (time-second diff) (time-nanosecond diff)))))
     (list 100 200 300 400))

This entry was posted on Monday, April 25th, 2005 at 9:07 pm and is filed under Programming. You can follow any responses to this entry through the comments RSS 2.0 feed. You can leave a response, or trackback from your own site.

16 Responses to “Solution to SICP Exercise 1.14”

1. Scott says:
   

   Hi Ken,

   My wife and I both agree with you on space being O(n), but we also think the steps (or “time”) is O(n) as well. Our reasoning is: the limiting case is where the change is all pennies (for both space and steps) and increasing the amount by ’1′ will add one step and one “unit” (expression) of space. So steps, as well as space, is linear with amount (and amount is synonymous with n in this exercise).

   Dei gratia,
   Scott

   July 23rd, 2007 at 7:19 pm
2. SICP по-русски » Blog Archive » Решение упражнения 1.14 из SICP says:
   

   [...] отметить, что и у Эли Бендерски, и у Кена Дика решение этого упражнения в части оценки числа шагов [...]

   August 27th, 2007 at 2:10 pm
3. mats says:
   

   According to my tests, the number of steps for count-change 11 is 55, count-change 22 is 250, count-change 44 is 1351, and count-change 88 is 11260.

   This seems to be O(n^3).

   November 4th, 2007 at 3:26 am
4. Chris says:
   

   You did (cc 6 2) wrong.

   December 6th, 2007 at 1:05 am
5. Bhrgunatha says:
   

   I agree with Chris – I think the 6.2 rhs should branch to (cc 1,2).
   Here is my attempt : SICP ex 1.14

   January 14th, 2008 at 9:08 am
6. Tim Eichner says:
   

   I agree that the space required is O(n), but I suspect that the number of steps is O(n^c), where n = amount and c = number of kinds of coins. For each kind of coin at position k with value v, you get about n/v steps with k kinds of coins. For each of these steps, you repeat the cc procedure with (k – 1) kinds of coins (with amounts between 0 and n). For large n, n/v is on the order of n, and (cc n k) amounts to multiplying n by itself k times.

   February 18th, 2008 at 10:25 pm
7. Tim Eichner says:
   

   If you find anything wrong with my previous argument, let me know; I’m curious about this ;) Not every step repeats the cc procedure with amount = 0 to n, of course; and (cc n k) multiplies n by itself about (k – 1) times. I can be fuzzy with details.

   February 19th, 2008 at 4:00 am
8. Tony says:
   

   I have a (rough) proof that the number of function calls is THETA(n^c) where c is the number of types of coins. I can send you this as a PDF if you email me off blog.

   Sketch: use induction and assume that the number of function calls is THETA(n^c) for c coins. Then show that the number of calls with c+1 types of coins is a function of the number with c coins, but with a sum term. Then use the binomial theorem and the fact that a sum of integer powers of degree x is a polynomial of degree x+1, to show that the sum leads to a polynomial of degree c+1. The PDF is much more detailed.

   Space is THETA(n) since you only ever need to keep track of the nodes above the current position and the longest possible path to a leaf is linear in n.

   October 23rd, 2008 at 6:02 am
9. Ken Dyck says:
   

   For anybody who is interested in Tony’s proof, you can find it here:
   http://sicp.org.ua/sicp/Exercise1-14?action=AttachFile&do=view&target=countingcoins.pdf

   Thanks letting us know about it, Tony.

   October 24th, 2008 at 7:17 pm
10. foobarage says:
    

    i would not claim to understand tony’s proof, but i think i have an other one for O(n^c)

    use a simplified cost-function
    t(n,c) = 1 : if k<=1 or n <= 1
    t(n-c,c) + t(n , c-1 ) + 1 : else

    (that is : it is using denominations [1,2,3,...,c] which is more costly than the ones in the orig program, corner cases are cut )

    lemma : (n-c)^c = (n-c)*(n-c)^(c-1) =2

    now :
    a*n^c = a* ( (n-1)*n^(c-1) + n^(c-1))
    with lemma
    >= a* ( (n-c)^c + n^(c-1) )
    with a=2
    > (n-c)^c + n^(c-1) +1

    and thats it – but i’m a dropout, so take with caution

    July 3rd, 2009 at 10:44 am
11. foobarage says:
    

    the internet ate my lemma
    it should be :
    (n-c)^c
    = (n-c)*(n-c)^(c-1)
    “is less than or equal” (n-1)*n ^ (c-1)

    for c >= 2

    sorry

    July 3rd, 2009 at 10:53 am
12. Improved Means For Achieving Deteriorated Ends / SICP Section 1.2 says:
    

    [...] my solution I was lucky to find a correct tree image which I will steal with credit. Thanks, Bhrgunatha. Here is the [...]

    April 14th, 2010 at 12:11 pm
13. Paul Blair says:
    

    @foobarage : I don’t think your lemma necessarily holds for cases in which n is less than c, and c is even. (n-c)^c could then be larger than (n-1) * (n^(c-1)). For example, if n is 1 and c is 4, then (n-c)^c is 81. But the other side of the expression is zero.

    October 5th, 2010 at 12:48 pm
14. Paul Blair says:
    

    @Tony I was able to follow your proof until you got to the Binomial Theorem, and then the math is a bit beyond what I can handle. One thing I didn’t understand, though — when you indicate the binomial coefficients you have the k on top and the i on the bottom. Having looked this up, I read that ( n k ) — i.e., n on top and k on the bottom — “is interpreted as the number of k-element subsets of an n-element set, that is the number of ways that k things can be ‘chosen’ from a set of n things. Hence, ( n k ) is often read as ‘n choose k’ and is called the choose function of n and k.”

    I’m not entirely sure if this affects the actual calculation, because I don’t really follow the expansion. So maybe it’s just a typo, or I’m not understanding something.

    October 5th, 2010 at 6:17 pm
15. Tony says:
    

    @Paul Blair Yep that’s a typo — well spotted. I think there is a shortcoming of the proof elsewhere too, in that I assume the induction holds only for n>n0, when it needs to hold for n>0. As it turns out, you can assume it holds for all n>0, then show that it does in the base case (it does), so it’s not fatal, but the PDF doesn’t do that.

    December 29th, 2010 at 1:29 am
16. timothy says:
    

    Claim: cc(n, c) is theta(n^c) where c is the number of denominations of coins.

    By induction on c. The case c = 1 is clear.

    Let d be the top denomination and write n = qd + r, with q, r non-negative and r < d. Note that, as functions of n, q is theta(n) and r is theta(1).

    Using the recursive algorithm, keep expanding cc(-, c) to get
    cc(n, c) = cc(n, c-1) + cc(n-d, c)
    = cc(n, c-1) + cc(n-d, c-1) + cc(n-2d, c)
    = …
    = cc(n, c-1) + cc(n-d, c-1) + … + cc(n-(q-1)d, c-1) + cc(n-qd, c),
    and since n-qd = r which is < d, we get cc(n-qd, c) = cc(n-qd, c-1) for the last term.

    Altogether cc(n, c) = the sum as i goes from 0 to q of cc(n-id, c-1).

    As long as the smallest denomination is 1, cc is non-decreasing. So the terms of the summation are arranged from biggest to smallest. There are q+1 terms and the biggest is cc(n, c-1).

    Thus an upper bound for cc(n, c) is (q+1)*(cc(n, c-1)). Since q is O(n) and cc(n, c-1) is O(n^(c-1)) by induction, this implies that cc(n, c) is O(n^c).

    Getting a lower bound for cc(n, c) is a little more tricky. Basically, we'll take the first half of the summation and note that we still have theta(n) terms, each of which can be bounded below by the last term we take, and this term is itself still theta(cc(n, c-1)).

    Let q' be the integer part of q/2. A lower bound for cc(n, c) is the sum of the first q' terms, and each of these terms is bounded below by the q'+1'st term which is cc(n-q'd, c-1). Thus a lower bound for cc(n, c) is q'*cc(n-q'd, c-1).

    Note that q' is theta(q/2) = theta(q) = theta(n), and n-q'd is also theta(n) since it's sandwiched between n and n/2. Convince yourself that if g is theta(n) and f is monotonic and polynomial, then theta(f(g)) = theta(f). So cc(n-q'd, c-1) is theta(cc(n, c-1)) = theta(n^(c-1)) by induction. Putting it all together with the lower bound, it follows that cc(n, c) is omega(n^c).

    Hence cc(n, c) is theta(n^c).

    May 9th, 2012 at 1:12 am

Leave a Reply