Homework Assignment 3

CS 2360
Winter 1997
Homework Assignment 3
Due no later than 8:00am, Monday, February 3, 1997

The car/cdr recursion that we discussed in class previously 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 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".  (Sometimes tree recursion is also called "deep recursion".) 

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.  

1)  The function "foo" is defined by the rule that foo(n) = n if n is 
    less than 3 and foo(n) = foo(n-1) + 2*foo(n-2) + 3*foo(n-3) if n is
    greater than or equal to 3.  Implement the function "foo" in 
    Common LISP.

2)  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.

3)  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.

4)  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.

5)  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)))

6)  Common LISP's "subst" function substitutes every occurrence of some
    specified element in an arbitrarily complex nested list structure
    with some other specified element.  In the example below, every
    occurrence of the symbol "a" is replaced by the symbol "x".

    ? (subst 'x 'a '(a (b a (c a) a b) a))
    (X (B X (C X) X B) X)

    However, because of the default use of the "eql" predicate, we 
    don't see the result we might expect in the following example:

    ? (subst 'x '(c a) '(a (b a (c a) a b) a))
    (A (B A (C A) A B) A)

    Use Common LISP to construct your own version of "subst" which
    behaves as described above.  Call it "my-subst".

7)  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 '()) => ()

8)  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.)

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

10) 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?

11) 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 1997 by Kurt Eiselt.  
All rights reserved.