CS 61A Spring 1995 Midterm 2 solutions
1. Box & pointer diagrams
> (cddaar '(((a b c d e) (f g h i j))
((l m n o p) (q r s t u))))
(C D E)
(car '(((a b c d e) (f g h i j))
((l m n o p) (q r s t u))))
===> ((a b c d e) (f g h i j))
(car '((a b c d e) (f g h i j)))
===> (a b c d e)
(cdr '(a b c d e)) ===> (b c d e)
(cdr '(b c d e)) ===> (c d e)
The box and pointer diagram for this is just
+++ +++ +++
        /
>    >   >   / 
          / 
+++ +++ +++
  
V V V
C D E
> (cons '(a b) (append '(c d) '(e f)))
((A B) C D E F)
Some people said ((a b) . (c d e f)) but Scheme never prints the
sequence ". (" in representing a list structure.
In the picture below, the starred pair is the one created by
the CONS invocation.
***********
*+++* +++ +++ +++ +++
*  *            /
>*   >   >   >   >   / 
*   *               / 
*+++* +++ +++ +++ +++
**********    
 V V V V

 C D E F

V
+++ +++
     /
   >   / 
      / 
+++ +++
 
V V
A B
Scoring: onehalf point for each printed result, onehalf point for
each box & pointer diagram, rounded down.
2. Type of last element of each result.
> '(list (count 'hello))
(LIST (COUNT 'HELLO))
So the last element is the (sub)list (COUNT 'HELLO).
> LIST
> '(list count)
(LIST COUNT)
So the last element is the word COUNT.
> NONNUMERIC WORD
> (list 'count count)
(COUNT #)
So the last element is the procedure named count.
> PROCEDURE
> (list 'hello (count 'hello))
(HELLO 5)
So the last element is the number 5.
> NUMBER
Scoring: One half point each, rounded down.
3. Treeaccumulate.
Here is the solution we were expecting:
(define (treeaccumulate fn tree)
(if (null? (children tree))
(datum tree)
(fn (datum tree) (forestaccumulate fn (children tree)))))
(define (forestaccumulate fn forest)
(if (null? (cdr forest))
(treeaccumulate fn (car forest))
(fn (treeaccumulate fn (car forest))
(forestaccumulate fn (cdr forest)))))
Alternatively, it can be done using other higherorder functions, especially
if you learned about REDUCE in CS 3:
(define (treeaccumulate fn tree)
(if (null? (children tree))
(datum tree)
(fn (datum tree)
(reduce fn (map (lambda (t) (treeaccumulate fn t))
(children tree))))))
REDUCE takes a function and a list (a sequence, not a tree!) and
accumulates (fn element1 (fn element2 (... (fn elementn1 elementn)...)))
Forestaccumulate has a slightly messier than usual base case, because
there must be at least one tree in the forest in order to get an answer.
(You can't assume that the identity element for FN is zero; that's true
for +, and you might think it's true for MAX if you forget about negative
numbers, but zero isn't the identity for * (1), SENTENCE ('()), WORD (""),
or lots of other possible functions. But we only took off one point for
any basecase confusion.
*** RESPECTING THE DATA ABSTRACTION DOES **NOT** MEAN SAYING "DATUM" WHENEVER
*** YOU MEAN CAR, AND "CHILDREN" WHENEVER YOU MEAN CDR!! That is precisely
DISrespecting the data abstraction! Respecting it means to distinguish
between a tree, whose component parts are called datum and children, and other
data types that have other component parts, such as forests (car and cdr, since
a forest is just a particular kind of sequence), rational numbers (numer and
denom), and so on.
The most common mistake was to ignore the tree abstraction and do a car/cdr
recursion, assuming that the leaves of the tree must be words:
(define (treeaccumulate fn tree) ;; wrong!
(cond ((null? tree) something)
((atom? tree) tree)
(else (fn (treeaccumulate fn (car tree))
(treeaccumulate fn (cdr tree))))))
It makes it **WORSE**, not better, if you say "datum" instead of car and
"children" instead of cdr in this procedure. All such solutions got at
most two points. Notice that the second argument to treeaccumulate is
supposed to be a tree. Neither (datum tree) nor (children tree) is a tree!
Therefore neither can be a valid argument to treeaccumulate.
Scoring: Broadly speaking the scale is the usual
5 correct
34 has the idea
12 has an idea
0 other
In this problem, "has the idea" means doing a tree recursion respecting
the tree abstraction. Solutions with only a base case problem, or some
small notation problem, got 4 points; more serious errors that still
showed an understanding of what an abstraction means got 3.
2point solutions came in two main categories: car/cdr recursions, as
described above, and sequential (nontree) recursions that respected the
abstraction. For example:
(fn (datum (car (children tree)))
(forestaccumulate fn (cdr (children tree))))
1point solutions were too diverse to list; one interesting case was the
use of a BINARY tree abstraction (with leftbranch and rightbranch); we
took this to mean copying from the text without understanding.
The most noteworthy 0point solutions were those that built a specific
example (like the functions + and max) into the program.
Just in case you're still thinking "but my procedure works!" think about
this example:
> (treeaccumulate (lambda (a b) (if (> (count a) (count b)) a b))
(makenode '(new york)
(list (makenode '(albany) '())
(makenode '(new hyde park) '())
(makenode '(new york) '())
(makenode '(yorktown heights) '()))))
(NEW HYDE PARK)
Your car/cdr procedure probably gives the incorrect answer YORKTOWN.
4. Manifest type/datadirected sets
(a) Typed empty sets.
(define (makeemptyunorderedset)
(attachtype 'unordered '()))
(define (makeemptyorderedset)
(attachtype 'ordered '()))
Scoring: 2 if correct, 1 if the right answer but violating the manifesttype
data abstraction or if the set isn't empty, 0 if even worse.
Several people wondered what's the point of indicating ordered or unordered
if the set is empty. That's a good question; the answer is that once we
use adjoinset, we'll have a typed nonempty set.
(b) datadirected elementofset?
We expected one of two possible answers. One uses get and put:
(put 'element? 'ordered elementoforderedset?)
(put 'element? 'unordered elementofunorderedset?)
(define (elementofset? elt set)
((get 'element? (type set)) elt (contents set)))
The other uses an association list:
(define (elementofset? elt set)
((cadr (assq (type set)
(list (list 'ordered elementoforderedset?)
(list 'unordered elementofunorderedset?))))
elt
(contents set)))
A solution would *not* be considered datadirected if it looks like
(define (elementofset? elt set) ;; wrong
(cond ((eq? (type set) 'ordered) ...)
...))
Scoring:
3 correct
2 datadirected, not quite right
1 datadirected but very wrong, or
right or almost right but not datadirected
0 not right, not datadirected
A typical onepoint solution was one in which elementofset? takes only
one argument, but uses GET to select a procedure (also called with only
one argument). We figured this means you at least know what the phrase
"datadirected" means but just copied an example from the book without
thinking about the fact that this problem is about a twoargument procedure.
5. Messagepassing characters
The solution we wanted was
(define (subscript char)
((char 'reposition) (makepoint 0 3)))
The crucial point in solving this problem was to understand what a
"character" is. A character is an abstract data type, represented in
this project by a procedure. Two other things that are *not* characters:
* a command list like '((forward 5) (right 90)) is not a character.
* some lines drawn on the computer screen are not a character!
So "having the idea" in this problem means that your procedure takes
a character (a procedure) as its argument and returns a character (a
procedure).
Scoring:
5 correct
4 ((char 'reposition) something)
3 returns a character
2 does (char 'reposition) but doesn't invoke the result
returns an oldstyle character (not messagepassing)
(char 'reposition extraarguments)
(somechar 'draw)
takes a command list as argument
1 even worse
0 even *worse*