As with the previous assignments, 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, no
LET, no SET!, 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. Follow the
style and documentation guidelines that we will be providing soon.
Don't forget to include that collaboration statement up front.
To construct these functions, you may use DEFINE, COND, IF, CAR, CDR,
CONS, EQUAL?, =, >, <, >=, <=, NULL?, LIST?, PAIR?, +, -, *, /, AND,
OR, NOT, QUOTE (or '), MEMBER, and REVERSE. You may not need all of these,
but they are all available to you. You may also use (or reuse) any function
which you have defined.
And in case you weren't sure, all the functions you write as
solutions to the following problems are to be written in Scheme.
The first eight problems are just more simple recursion practice.
The good stuff comes after problem 8.
1) The function SET-DIFFERENCE takes two lists as arguments and
returns a list of top-level elements of the first argument
that do not appear in the second argument. Create
SET-DIFFERENCE using only augmenting recursion.
> (set-difference '(a b c) '(b c d))
(a)
> (set-difference '(b c d) '(a b c))
(d)
> (set-difference '(a b) '(c d))
(b a) ;; order is unimportant
2) Now create another version of SET-DIFFERENCE using only tail
recursion. Call this function SET-DIFFERENCE-TR.
3) SUBSET? is a predicate that takes two lists as arguments and
returns #t if every top-level element of the first argument
appears as a top-level element in the second argument. It
returns #f otherwise. Create SUBSET? using only augmenting
recursion.
> (subset? '(c d) '(a b c d))
#t
> (subset? '(c d) '(d c b a))
#t
> (subset? '(a b c) '(b c d))
#f
> (subset? '(c d) '())
#f
> (subset? '() '(c d))
#t
4) Now create another version of SUBSET? using only tail
recursion. Call this predicate SUBSET-TR?.
5) MAKE-LIST is a function that takes two arguments. The
first argument is a non-negative integer (let's call it N)
and the second argument is anything. MAKE-LIST creates and
returns a list of N copies of the second argument.
Create MAKE-LIST using only augmenting recursion.
> (make-list 3 'ha)
(ha ha ha)
> (make-list 3 ())
(() () ())
> (make-list 0 'ha)
()
> (make-list 2 '(help (me)))
((help (me)) (help (me)))
>
6) Now create another version of MAKE-LIST using only tail
recursion. Call this predicate MAKE-LIST-TR.
7) SUBSTITUTE is a function that takes three arguments. Let's
call the first argument new-item and the second argument
old-item. The third argument is a list. SUBSTITUTE creates
a copy of the third argument in which all top-level occurrences
of old-item have been replaced by new-item. Create SUBSTITUTE
using only augmenting recursion.
> (substitute 'x 'a '(a b a c a d))
(x b x c x d)
> (substitute 'x 'a '())
()
> (substitute 'x 'a '(a b (a c) a d))
(x b (a c) x d)
>
8) Now create another version of SUBSTITUTE using only tail
recursion. Call this predicate SUBSTITUTE-TR.
The type of recursion that is at the heart of the remainder of this
homework assignment 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. While collaboration is completely acceptable, 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, and then adapted to the Scheme dialect we're using:
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 Scheme 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:
(define (move-tower size from to extra)
(cond [(= size 0) #t]
[else (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:
(define (print-move from to)
(newline)
(display "move top disk from peg ")
(display from)
(display " to peg ")
(display to))
(Note two things. First, we haven't told you anything about input
or output. Look up "newline" and "display" 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).
9) 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
Scheme.
10) Construct a Scheme function, using car/cdr recursion again, called
"sum-all", which sums all the numeric values in a list, no matter
how deeply those values may be nested in the list, and returns
that value. For example:
(sum-all '(((1) 2 A (3 B (4))))) => 10
(sum-all '()) => 0
You may NOT assume that all the items in the list will be numbers.
(We did this one in class.)
11) Construct a Scheme 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 values 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 '()) => ()
You may NOT assume that all the items in the list will be numbers.
12) When we apply the Scheme 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.
13) Construct a Scheme function called "insert-left-all" which takes
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 '()) => ()
14) 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 Scheme function called "fib"
which takes one argument, an integer, and returns the appropriate
Fibonacci number as determined by the rule above.
15) Now construct the tail recursive version of "fib". Call it
"fib-it".
16) While using Scheme's "trace" and "time" functions, run both versions
of your Fibonacci function on a reasonably big number, like 8, and see
what Scheme 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?
17) 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 Scheme 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 Scheme. 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.
18) 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 Scheme 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 (c) 2003 by Kurt Eiselt. All rights reserved, with
the exception of stuff that belongs to somebody else.
Last revised: September 29, 2003