CS 2360/4730
Midterm 1 Fall 1995
Please write your name on the upper right hand corner of this page.
There are 90 points possible on this exam. You have 80 minutes to
complete it. Put only what you want to be graded on the front sides
of the pages, and use the back sides of the pages as scratch paper.
If you run out of room on the front side of the page, you can put
part of your answer on the back of that same page, but make sure
you note on the front of the page that there's stuff to be graded
on the back. And please strive for legibility, because we don't
give credit for stuff we can't read. For this exam, use only
recursive or applicative programming techniques as indicated in
the individual problems. Don't use traditional iterative methods
(no loop, do, dolist, dotimes, etc.).
So that we can post your scores on the newsgroup, we'd like you to
provide us with a super secret identification code (of no more than
eight characters) that will allow you to find your scores without
anyone else knowing which scores are yours. If you want us to post
your scores on the newsgroup, please print your code in the space
below. If you don't want us to post your scores, just leave the
space blank.
___________________________
1. (10 points) Here's a sample of a database for keeping track of
baseball statistics:
((KLESKO 44 13 17 5)(LOPEZ 49 5 14 3)(JUSTICE 33 3 9 2))
Each five-element sublist in this structure contains all the data
we're interested in for a given player. The first element is the
player's last name. The second element is his number of times at
bat. The third element is the number of runs he has scored. The
fourth element is his total hits. The fifth element is his number
of home runs.
One could use some of this information to determine a player's
batting average, which is computed by dividing the player's hits by
the player's times at bat. Your job now is to use Common LISP,
while employing good procedural and data abstraction techniques, to
construct a function called determine-batting-averages. This function
takes only one argument, the database above, and returns a list of
two-element lists. In each of the two-element lists, the first element
is the player's name, and the second element is the player's batting
average. Here's an example:
? (determine-batting-averages
'((KLESKO 44 13 17 5)(LOPEZ 49 5 14 3)(JUSTICE 33 3 9 2)))
((KLESKO 0.386) (LOPEZ 0.286) (JUSTICE 0.273))
Oh, one other thing. Just to make this interesting, we're requiring
you to use mapcar to provide the basic control structure for this function.
2. (10 points) Remember the flatten function? For this problem,
you are to define a slightly different version of flatten, which we'll
call flatten-with-depth. Just like flatten, flatten-with-depth
takes one argument, a hierarchical list structure of arbitrary depth, and
removes the hierarchical structure. But instead of just returning a list
of atoms, as flatten does, flatten-with-depth returns a list of two-element
lists, where the first element of each pair is an atom from the input
list structure, and the second element is a number representing the depth
of the atom in the original structure. In other words, flatten works
like this:
? (flatten '(a (b (c) d ((e)))))
(A B C D E)
?
but flatten-with-depth works like this:
? (flatten-with-depth '(a (b (c) d ((e)))))
((A 0) (B 1) (C 2) (D 1) (E 3))
?
In the space below, define your own version of flatten-with-depth in
Common LISP such that it behaves as just described.
3. (10 points) Think about flatten-with-depth again. Can you
construct a function in Common LISP which when given the output from
flatten-with-depth will return the original list structure (i.e., the
input to flatten-with-depth)? Let's say we call this function unflatten.
It would work like this:
? (unflatten '((a 0) (b 1) (c 2) (d 1) (e 3)))
(A (B (C) D ((E))))
?
If such a function is possible, construct unflatten in the space below.
If you think it is not possible to construct this function, provide a
convincing argument as to why it can't be done.
4. (10 points) Below is one possible definition of reverse which uses
append and list:
(defun reverse (r-list)
(cond ((null r-list) nil)
(t (append (reverse (rest r-list))
(list (first r-list))))))
Using the substitution model of evaluation described in class, illustrate
the shape of the process generated by evaluating the expression
(reverse '(a b c)).
5. (10 points) Now construct a new version of reverse which is
tail-recursive. Use the substitution model of evaluation to
illustrate the shape of the process generated by this new
version when evaluating (reverse '(a b c)).
6. (10 points) Here are some questions you might be able to answer
(with no more than two sentences each, please) even if you can't write
an iota of LISP code:
a) What's functional programming?
b) What's a side effect?
c) What's abstraction?
d) What's reference?
e) What's synthesis?
f) What's the difference between a procedure and a process?
g) What's the "shape" of a process?
h) What's the difference between tail recursion and augmenting recursion?
i) How does the difference between tail recursion and augmenting
recursion affect the shape of a process?
j) Why should programmers care about all of these issues?
7. (10 points) For magicians and other folks who make a living
with playing cards, one of the most difficult skills to master is
the perfect faro shuffle. If you wanted to perform the perfect
faro shuffle, you'd first have to cut the deck of cards exactly
in half, which in itself is not easy to do repeatedly. (This also
assumes that the deck contains an even number of cards.) Then you
would have to shuffle the two half-decks together so that the cards
are perfectly interleaved. That is, this newly-shuffled deck would
contain the first card from one half-deck, the first card from the
other half-deck, the second card from the first half-deck, the second
card from the other half-deck, and so on.
Since performing the perfect faro shuffle is so difficult, what you're
going to do here and in the next two problems is construct the perfect
faro shuffle simulator, in Common LISP of course. The first component of
the simulator will be the cut-deck function, which takes one argument:
a list containing an even number of elements which represent the cards
in a deck. The cut-deck function returns a list which consists of two
sublists; the first sublist corresponds to the "top-half" of the original
deck, and the second sublist corresponds to the "bottom-half" of the
original deck. For example:
? (cut-deck '(A K Q J 10 9))
((A K Q) (J 10 9))
Hint: LISP's subseq function might be useful.
8. (10 points) Now that you've separated the deck into two halves of
equal length, you'll want to shuffle them. So it's time to construct
the second component of the simulator, the shuffle-halves function.
This function also takes one argument, which is a list containing two
equal-length sublists, just like what the cut-deck function from Problem 7
returns. (Coincidence? I think not.) The shuffle-halves function
returns one list which consists of the perfectly-interleaved elements
of those two sublists from the input. For example:
? (shuffle-halves '((A K Q) (J 10 9)))
(A J K 10 Q 9)
9. (10 points) What makes the perfect faro shuffle so useful is that
if you apply it enough times to a deck of cards, you'll eventually restore
the order of the cards to what it was before you began shuffling! For
example, if you take a brand new deck of 52 cards (after you toss away
the jokers and the advertising), and then apply the perfect faro shuffle
eight times, the order of those cards will be exactly the same as it was
when you took the cards out of the box. Using the perfect faro shuffle,
a magician can unwrap a new deck of cards, ask someone to pick a card
from the deck, have that person put the card back elsewhere in the deck,
shuffle the deck eight times, and locate the selected card immediately
by just looking to see which card is out of order. For a gambler, the
perfect faro shuffle is even more useful, as the gambler can shuffle a
new deck eight times, thereby convincing the other players that the
cards have been thoroughly mixed up, when in fact the gambler knows
that the cards are arranged in exactly the order that they were in before
the shuffling started. That knowledge provides a significant advantage
at the poker table.
To finish up the simulator, construct a function called faro-shuffle
which takes one argument: a list containing an even number of elements
which represent the cards in a deck. The faro-shuffle function then
uses cut-deck and shuffle-halves repeatedly to simulate the shuffling of
the simulated deck of the simulated cards, and then returns the number
of times that the deck was shuffled to restore it to its original order.
For example:
? (faro-shuffle '(A K Q J 10 9))
4
Note that faro-shuffle does not return the simulated deck. Why?
Because it's the same as the deck that was originally passed to it.
Got it? Good.
The cheat sheet
(first '(a b c d e)) => a
(second '(a b c d e)) => b
(third '(a b c d e)) => c
(fourth '(a b c d e)) => d
(fifth '(a b c d e)) => e
(rest '(a b c d e)) => (b c d e)
(cons 'a '(b c d e)) => (a b c d e)
(cons '(a) '(b c d e)) => ((a) b c d e)
(append '(a b) '(c d)) => (a b c d)
(list 'a 'b 'c) => (a b c)
(list 'a) => (a)
(list '(a b) '(c d)) => ((a b) (c d))
(length '(a b c d e)) => 5
(length nil) => 0
(subseq '(a b c d e) 0 2) => (a b)
(subseq '(a b c d e) 0 4) => (a b c d)
(subseq '(a b c d e) 1 2) => (b)
(subseq '(a b c d e) 1 4) => (b c d)
(subseq '(a b c d e) 2 2) => nil
(subseq '(a b c d e) 2 4) => (c d)
(member 'c '(a b c d e)) => (c d e)
(remove-duplicates '(a b a c a d)) => (b c a d)
(remove-duplicates '(a b (a c) a d)) => (b (a c) a d)
(reverse '(a b c)) => (c b a)
(reverse '(a (b c) d) => (d (b c) a)
(remove 'a '(a b a c a d)) => (b c d)
(remove 'a '(a b (a c) a d)) => (b (a c) d)
(substitute 'x 'a '(a b a c a d)) => (x b x c x d)
(substitute 'x 'a '(a b (a c) a d)) => (x b (a c) x d)
(intersection '(a b c) '(b c d)) => (b c)
(union '(a b c) '(b c d)) => (a b c d)
(make-list 3) => (nil nil nil)
(assoc 'a '((c d)(a b)(e f))) => (a b)
(assoc 'c '((c d)(a b)(e f))) => (c d)
(insert 'a '(b c d e) 0) => (a b c d e)
(insert 'a '(b c d e) 2) => (b c a d e)
(insert 'a '(b c d e) 4) => (b c d e a)
(nthcdr 0 '(a b c)) => (a b c)
(nthcdr 2 '(a b c)) => (c)
(nthcdr 4 '(a b c)) => nil
(last '(a b c d)) => (d)
(last '(a b (c d))) => ((c d))
(last nil) => nil
(* 4 2) => 8
(+ 4 2) => 6
(/ 4 2) => 2
(- 4 2) => 2
(sqrt 25) => 5
(null '()) => T
(null '(a b c)) => nil
(atom 'a) => T
(atom '(a b c)) => nil
(listp 'a) => nil
(listp '(a b c)) => T
(eql 'a 'a) => T
(eql '(a b) '(a b)) => nil
(equal 'a 'a) => T
(equal '(a b) '(a b)) => T
(mapcar #'sqrt '(16 25 36)) => (4 5 6)
(cond ( *test1* *action1*)
:
:
( *testn* *actionn*))
(defun *function-name* *argument-list* *function-body*)
Copyright 1997 by Kurt Eiselt. All rights reserved.
Last revised: January 22, 1997