CS 2360
Fall 1998
Homework Assignment 3
Due no later than 8:00am, Monday, October 19, 1998
This assignment comes in two parts. And the good news is that you've
already done half of the first part (assuming you were able to solve
the appropriate problems in the first homework assignment).
And let me take a moment to reiterate what I told you last week
(these guidelines will be in effect for several more weeks):
For all these problems, make sure that you adhere to the constraints
of the functional programming paradigm (e.g., access only information
passed as parameters, return one value, no side effects, etc.).
Furthermore, remember that you're programming for people, not for the
benefit of the computer. Write your code so that other people can
understand it easily. That means you should worry about modularity
and abstraction where appropriate, and you should employ meaningful
function and parameter names. Don't forget to document your code
with appropriate comments, and it wouldn't hurt to use indentation
to make your code look pretty (which in turn makes for happier and
more generous graders).
Part One:
For each of the problems in Part One, you are to provide two solutions:
one solution should use only augmenting recursion, and the other should
use only tail recursion.
To construct these functions, you may use DEFUN, COND, IF, NULL, ATOM,
LISTP, NUMBERP, FIRST, REST, CONS, LIST, ZEROP, SYMBOLP, CONSP, the
equality predicates (EQ, EQL, EQUAL, EQUALP, and =), the inequality
predicates, QUOTE (or '), the arithmetic functions (+, -, *, and /), and
the Boolean functions (AND, OR, and NOT). You may not need all these
functions, but they are available to you. You may also use (or reuse) any
function which you have defined. Furthermore, if you must construct
additional functions in support of your solutions, and those functions
are recursive, make sure you provide both augmenting recursion
and tail recursion versions. Don't use assignment, and don't use any
control structure other than recursion.
Here are the functions we want you to construct:
1 and 2) my-append
(my-append '(a b) '(c d)) => (a b c d)
Write two versions of my-append, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive version
my-append-tr.
3 and 4) my-remove-duplicates
(my-remove-duplicates '(a b a c a d)) => (b c a d)
(my-remove-duplicates '(a b (a c) a d)) => (b (a c) a d)
Write two versions of my-remove-duplicates, one using augmenting
recursion and one using only tail recursion. Call the tail-recursive
version my-remove-duplicates-tr.
5 and 6) my-intersection
(my-intersection '(a b c) '(b c d)) => (b c) ; order is unimportant
Write two versions of my-intersection, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive
version my-intersection-tr.
7 and 8) my-make-list
(my-make-list 3) => (nil nil nil)
Write two versions of my-make-list, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive
version my-make-list-tr.
9 and 10) my-assoc
(my-assoc 'a '((c d)(a b)(e f))) => (a b)
(my-assoc 'c '((c d)(a b)(e f))) => (c d)
Write two versions of my-assoc, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive
version my-assoc-tr.
11 and 12) my-nthcdr
(my-nthcdr 0 '(a b c)) => (a b c)
(my-nthcdr 2 '(a b c)) => (c)
(my-nthcdr 4 '(a b c)) => nil
Write two versions of my-nthcdr, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive
version my-nthcdr-tr.
13 and 14) my-last
(my-last '(a b c d)) => (d)
(my-last '(a b (c d))) => ((c d))
(my-last nil) => nil
Write two versions of my-last, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive
version my-last-tr.
15 and 16) my-reverse
(my-reverse '(a b c)) => (c b a)
(my-reverse '(a (b c) d) => (d (b c) a)
Write two versions of my-reverse, one using augmenting recursion
and one using only tail recursion. Call the tail-recursive
version my-reverse-tr.
Part Two
For all problems below, the constraints are the same as they are above.
If you believe that you need some LISP function that's not included in the
set of allowable functions, make your well-informed and convincing argument
to the newsgroup and see what your TAs say. (They'll probably say "build
it yourself".)
The type of recursion that is the heart of this part of the homework
involves breaking a problem into two smaller problems and recursively
calling itself on the two smaller problems. This type of recursion
has different names that all mean the same thing. Sometimes it's called
multiple recursion, sometimes tree recursion, sometimes deep recursion,
and sometimes car/cdr recursion.
These problems are designed to give you some practice with tree
recursion. As with the previous assignment, many of these problems have
been used in previous offerings of this course. Try to do them on
your own. Tree recursion is a very powerful technique, and your long-
term success in this course will be dependent in no small part on how
comfortable you become with this technique. And you're not going to
get comfortable with tree recursion if you can't do it by yourself.
Please make sure that you use the function names we tell you to use
when you define your functions.
To start, here's a discussion of a tree-recursive solution to the
Towers of Hanoi problem that may be of use to you when attacking
some of these other problems. The write-up was borrowed pretty much
verbatim from the Instructor's Manual to "Structure and Interpretation
of Computer Programs" by Julie Sussman, Harold Abelson, and Gerald Jay
Sussman.
There's a class of math (combinatorics) problems that are easily
solved using a divide-and-conquer approach which in turn can be
implemented in LISP via tree or multiple recursion. One classic
example of this type of problem is called "The Towers of Hanoi."
Assume that you have three pegs and a set of disks, all of different
diameters, with holes in them (so that they can slide onto the
pegs). Start with all the disks on a single peg, in order of
size (with the smallest on top). The object of the puzzle is to
move the pile of disks to a specified peg, by moving one disk at a
time. A legal move consists of taking the top disk from any peg
and putting it on either of the other two pegs; but a disk may
never be placed on top of a disk that is smaller than itself.
We construct here a procedure "move-tower" that takes four
arguments---the number of disks in the pile, the peg the disks are
on, the peg the disks should be moved to, and the extra peg---
and prints the sequence of moves. For example, consider moving
three disks from peg1 to peg3 by evaluating
(move-tower 3 1 3 2)
This should print:
move top disk from peg 1 to peg 3
move top disk from peg 1 to peg 2
move top disk from peg 3 to peg 2
move top disk from peg 1 to peg 3
move top disk from peg 2 to peg 1
move top disk from peg 2 to peg 3
move top disk from peg 1 to peg 3
If you try to solve this puzzle by thinking of individual moves
in a particular case (such as the one solved above), then you are
not likely to come up with a general solution (one that works for
any number of disks). You must find a way to think about the
problem in general. There is a powerful strategy (similar to
mathematical induction) for thinking about such problems, called
"wishful thinking" (which is just a form of abstraction). The idea
is to
decide what would make the problem simpler;
pretend you already know how to solve the simpler version of
the problem:
figure out how to use the solution of the simpler problem to
construct a solution to the original problem
In the case of The Towers of Hanoi, it's pretty clear what would
make the problem simpler, namely having fewer disks. So let's
assume that we know how to solve the puzzle for any number of
disks less than the number we've been asked to move. We can then
solve the puzzle in three steps:
move all but the bottom disk to the extra peg (by wishful
thinking), thus leaving the biggest disk behind
move the leftover (biggest) disk to the destination peg
move the pile of disks we stored on the extra peg to the
destination peg (which now has the biggest disk on it)
But we cannot always reduce the problem to a simpler one: There is
nothing easier than moving 0 disks. So if we are asked to move 0
disks, we'd better not try to follow the above steps; rather, we
should do nothing.
This plan can be directly translated into a procedure:
(defun move-tower (size from to extra)
(cond ((= size 0) T)
(t (move-tower (- size 1) from extra to)
(print-move from to)
(move-tower (- size 1) extra to from))))
"move-tower" tests whether it has been given the simplest case
the base case). If so, it just returns T (for lack of a more
useful value---no other procedure is using the returned value).
If not, it follows the recursive plan given above, using
"move-tower" for smaller numbers of disks (for which it is assumed,
by wishful thinking, to work).
The procedure "print-move" prints the sequence of moves to the
monitor. The moves appear in the order that they should be
carried out so as to move all the disks from one peg to the other
without putting larger disks on top of smaller disks:
(defun print-move (from to)
(terpri)
(princ "move top disk from peg ")
(princ from)
(princ " to peg ")
(princ to))
(Note two things. First, we haven't told you anything about I/O.
Look up "terpri" and "princ" and you'll know everything you need
to know for this example. Second, note that printing involves
side effects. The printing is included here so that the computation
itself produces something meaningful (a list of actions to be
performed) and you can follow what's going on. This is not,
however, a cue for you to start introducing side effects in the
stuff you turn in for grading.)
All the recursive procedures we've seen can be described in terms
of wishful thinking. The programs all have the same pattern: the
recursive step, which uses the solution to a simpler problem to
construct the solution to a given problem; and one or more base
steps, which handle the cases that arise when you simplify the
problem as in the recursive step.
Now let's begin the fun (and while it's fine to use the "flatten"
function as inspiration, don't actually call a function that "flatten"s
a list...your graders won't be happy).
17) 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.
18) 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.
19) 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 A (3 B (4))))) => 10
(sum-all nil) => 0
You may NOT assume that all the atoms in the list will be numbers.
20) Construct a LISP function, using car/cdr recursion yet again, called
"inc-all", which increments all the numeric values in a list by one,
no matter how deeply those atoms may be nested in the list, and
returns the list with those new values. For example:
(inc-all '(((1) 2 A (3 B (4))))) => (((2) 3 A (4 B (5))))
(inc-all nil) => nil
You may NOT assume that all the atoms in the list will be numbers.
21) 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.
22) 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)))
23) 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 '()) => ()
24) 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.)
25) Now construct the tail recursive version of "fib". Call it
"fib-it".
26) 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?
27) 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.
28) The game of poker uses a deck of 52 cards divided into four "suits"
called clubs, diamonds, hearts, and spades. Each suit has 13 cards:
ace, two through ten, and then the jack, queen, and king. A typical
poker hand consists of five cards drawn randomly. One particularly
desirable hand is called a "flush", in which all five cards are from
the same suit.
Poker players need to know the probabilities of being dealt a flush,
and to do that they need to know how many ways there are to select
five cards from the thirteen cards in a suit (among other things).
More generally, they need to know how many different sets of m cards
can be selected from n cards. Here's your chance to help the
world's poker players.
Write a Common LISP function called "flushes" which takes two
non-negative integers as arguments. The first argument represents
n or the number of cards in the suit (e.g., 13), while the second
argument represents m or the number of cards in a hand (e.g., 5).
Your function should then use multiple or tree recursion to compute
the number of flushes of size m that can be drawn from a suit
containing n cards and return that numeric value.
What's the formula for this one? Go back and get inspiration from
the problems above and see if you can figure it out for yourself.
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: October 14, 1998