CS 2360 Fall 1995 Homework Assignment 3 Due no later than 8:00am, Monday, October 16, 1995 The car/cdr recursion that we discussed in class today 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. 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".) The first seven problems are designed to give you some practice with tree or car/cdr recursion. The last problem gives you an opportunity to explore applicative programming. 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 A simple way to get the same result as count-atoms would be to do this: (length (flatten '(a (b c) (((d) e) f) g))) => 7 But that would be too easy...you wouldn't learn anything that way, so don't do it. Solve this problem by modifying flatten to do what you need. 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. A simple way to get the same result as sum-all would be to do this: (apply #'+ (flatten '(((1) 2 (3 (4)))))) => 10 But again that would be too easy...you wouldn't learn anything that way, so don't do it. Solve this problem by modifying flatten to do what you need. 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) Don't forget to use car/cdr recursion here. 4) 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. 5) Now construct the tail recursive version of "fib". Call it "fib-it". 6) 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. (For those of you using Macintosh Common LISP, make sure you go to the "environment" option in the "tools" menu and turn off the *compile-definitions* flag). 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? 7) 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. 8) The covariance of two lists of numbers, X and Y, of the same length, is defined as: E X Y / n - (E X /n)(E Y /n) i i i i ________________________________ n - 1 where X is the ith element of list X i Y is the ith element of list Y i n is the number of items in each list E is a crude representation for that nice sigma symbol from math that means summation Construct a LISP function to compute the covariance of X and Y. Use LISP's "apply" function to perform the summations. Use LISP's "mapcar" function to compute the crossproduct of X and Y, which is a list of the products X Y . i i Note that the function we constructed in class today is a very crude version of "mapcar". LISP's "mapcar" is much more flexible in that it takes functions that expect multiple arguments. For example, you can do stuff like this: ? (mapcar #'+ '(1 2 3) '(1 2 3)) (2 4 6) ? (mapcar #'+ '(1 2 3) '(1 2 3) '(1 2 3)) (3 6 9) ? -- Kurt Eiselt Assistant Dean, Student Services College of Computing Georgia Institute of Technology Atlanta, GA 30332-0280 http://www.cc.gatech.edu/aimosaic/faculty/eiselt.html