Homework Assignment 3

CS 2360
Spring 1996
Homework Assignment 3
Due no later than 8:00am, Monday, April 22, 1996
(please accept my apologies for not getting this out last night...
dial-up service from Rancho Eiselt just wasn't getting it done)


The car/cdr recursion that we discussed in class last Thursday involved 
a function that broke a problem into two smaller problems and 
recursively called itself on those two smaller problems.  It was called 
car/cdr recursion because the problem being worked on came in the form 
of a list, which was broken into component parts (car = first, cdr = 
rest).  We can use this same style of recursion on other problems, even 
though the problem may not come in the form of a list, as you'll see
below in problem 4.  In that case, we can't really call it car/cdr 
recursion.  Think of car/cdr recursion as a specialized version of 
something called "tree recursion".  (Some folks also refer to tree 
recursion as "deep recursion"...as if it didn't have enough names 
already.)

These problems are designed to give you some practice with tree 
recursion.  Each problem is worth 10 points.  Also, please 
make sure that you use the function names we tell you to use when you 
define your functions.  If your TA tries to test your function and it 
doesn't work because you've named it incorrectly, you won't be getting 
any credit for that problem.  

1)  Construct a LISP function called "count-atoms" which counts all the
    atoms in a list, no matter how deeply those atoms may be nested in
    the list, and returns that value.  For example:

    (count-atoms '(a (b c) (((d) e) f) g)) => 7
    (count-atoms nil) => 0

    Don't forget to use car/cdr (or tree) recursion in this function.

2)  Construct a LISP function, using car/cdr recursion again, called
    "sum-all", which sums all the numeric values in a list, no matter
    how deeply those atoms may be nested in the list, and returns
    that value.  For example:

    (sum-all '(((1) 2 (3 (4))))) => 10
    (sum-all nil) => 0

    You may assume that all the atoms in the list will be numbers.

3)  When we apply the LISP function "reverse" to a list, we get a new
    list with the top-level objects in reverse order.  For example:

    (reverse '(a (b c) (d (e f)))) => ((d (e f)) (b c) a)

    Your job now is to construct a function called "reverse-all" that
    not only reverses the order of the top-level elements of the list
    but also reverses the order of the elements at each nested level
    within the sublists, as follows:

    (reverse-all '(a (b c) (d (e f)))) => (((f e) d) (c b) a)

    Once again, use car/cdr recursion here.

4)  Use car/cdr recursion to construct a LISP function called 
    "remove-all" which removes all occurrences of an item from a list.
    For example:

    (remove-all 'a '((a b (c a)) (b (a c) a))) => ((b (c)) (b (c)))

5)  Construct a LISP function called "insert-left-all" which takes a
    one item (the first argument) and inserts it to the immediate left
    of each occurrence of another item (the second argument) in a list
    (the third argument).  For example:

    (insert-left-all 'z 'a '(((a)))) => (((z a)))
    (insert-left-all 'z 'a '(a ((b a) ((a (c)))))) =>
      (z a ((b z a) ((z a (c)))))
    (insert-left-all 'z 'a '()) => ()

6)  Consider computing the sequence of Fibonacci numbers, in which each
    number is the sum of the preceding two:

    0, 1, 1, 2, 3, 5, 8, 13, 21, ...

    In general, the Fibonacci numbers can be defined by the rule

              /  0                    if n = 0
              |
    Fib(n) = (   1                    if n = 1
              |
              \  Fib(n-1) + Fib(n-2)  otherwise

    Thus, Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, Fib(4) = 3,
    Fib (5) = 5, and so on.  Construct a LISP function called "fib" 
    which takes one argument, an integer, and returns the appropriate
    Fibonacci number as determined by the rule above.  (Hint: the 
    answer is in your book by Graham, except that his algorithm for
    computing the Fibonacci numbers is slightly wrong.)

7)  Now construct the tail recursive version of "fib".  Call it 
    "fib-it".

8)  While using LISP's "trace" function, run both versions of your 
    Fibonacci function on a reasonably big number, like 8, and see
    what LISP displays.  What can you say about comparative shapes of 
    the processes spawned by the two different implementations of the 
    Fibonacci function?  What does this tell you about the memory 
    required by either version?  What does this tell you about the speed 
    of execution of either version?

9)  How many different ways can we make change for a dollar, given
    that we have half-dollars, quarters, dimes, nickels, and pennies
    available?  To solve this problem, you'll write a LISP function to
    be called "count-change" which will compute the number of ways to 
    count change given any amount of money.  This function will take 
    one argument, a number representing the amount of money to be 
    changed (e.g, 50 = 50 cents, 100 = one dollar).

    This problem has a simple solution as a recursive procedure.  
    Suppose we think of the types of coins available as arranged in
    some order.  Then the following relation holds:

      Number of ways to change amount A using N kinds of coins  =

      Number of ways to change amount A using all but the first
      kind of coin

        +

      Number of ways to change amount A - D using all N kinds
      of coins, where D is the denomination of the first kind of coin.

    To see why this is true, observe that the ways to make change can be
    divided into two groups:  those that do not use any of the first
    kind of coin, and those that do.  Therefore, the total number of 
    ways to make change for some amount is equal to the number of ways 
    to make change for the amount without using any of the first kind of 
    coin, plus the number of ways to make change assuming that we do use 
    the first kind of coin.  But the latter number is equal to the 
    number of ways to make change for the amount that remains after 
    using a coin of the first kind.  (Whew!)

    Thus, we can recursively reduce the problem of changing a given 
    amount to the problem of changing smaller amounts using fewer kinds
    of coins.  Consider this reduction rule carefully, and convince 
    yourself that we can use it to describe an algorithm if we specify 
    the following degenerate cases:

      If A is exactly 0, we should count that as 1 way to make change.

      If A is less than 0, we should count that as 0 ways to make 
      change.

      If N is 0, we should count that as 0 ways to make change.

    (To convince yourself that this works, work through in detail on 
    paper how the reduction rule applies to the problem of making change 
    for 10 cents using pennies and nickels.)

    So, now that we've done the hard part for you, construct the
    "count-change" function in LISP.  How many ways ARE there to make
    change for a dollar?  After you've built your "count-change" 
    function, just type (count-change 100) at your interpreter and find 
    out.



Copyright 1996 by Kurt Eiselt.  All rights reserved.