CS 2360
Winter 1998
Homework Assignment 3
Due no later than 8:00am, Monday, February 2, 1998
Undoubtedly you enjoyed the many problems we gave you last week,
so here's another bunch of them. For all problems below, the
constraints are the same as they were in the previous homework assignment
except that you can add LIST and the IF construct to your repertoire now.
(How does IF work? You could look it up.) As in the previous homework
assignment, each problem is worth 10 points. As before, continue to worry
about things like modularity, abstraction, meaningful function and parameter
names, reasonable comments, appropriate indentation, and so on.
If you believe that you need some LISP function that's not included in the
set of allowable functions from the previous assignment, make your
well-informed and convincing argument to the newsgroup and see what your TAs
say. (They'll probably say "build it yourself".)
The car/cdr recursion that we discussed in class last week 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 "multiple recursion" or
"deep 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.
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.
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 don't "flatten" anything):
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 A (3 B (4))))) => 10
(sum-all nil) => 0
You may NOT assume that all the atoms in the list will be numbers.
4) 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.
5) 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.
6) 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)))
7) 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 atom "a" is replaced by the atom "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,
the list "(c a)" is not replaced by the atom "x" when "subst"
is called like this:
? (subst 'x '(c a) '(a (b a (c a) a b) a))
(A (B A (C A) A B) A)
Why doesn't the substitution occur? Because the list "(c a)"
in the second argument is not "eql" to the list "(c a)" that
is embedded in the third argument. Got it? Good.
Use Common LISP to construct your own version of "subst" which
behaves as described in both cases above. Call it "my-subst".
(You can check any LISP book to see more examples of "subst"
in action.) [This problem rewritten on Feb. 1, 1998.]
8) 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 '()) => ()
9) 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.)
10) Now construct the tail recursive version of "fib". Call it
"fib-it".
11) 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?
12) 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.
13) 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: February 1, 1998