CS 61A Fall 1996 Midterm 2 solutions
1. expression trees
(a) Many people got confused about which abstract data type we're using.
As the problem clearly states, you are given the constructor MAKETREE
with two arguments, and the selectors DATUM and CHILDREN.
(define (treeify computation)
(if (number? computation)
(maketree computation '())
(maketree (cadr computation)
(list (treeify (car computation))
(treeify (caddr computation))))))
The most common errors were about the base case:
* Suppose the argument is a number. What should the result be?
IT MUST STILL BE A TREE! You can't just return the number;
numbers are not in the range of this procedure.
* The problem statement specifically says, "the argument to treeify
is a NONEMPTY list..." Many people always use NULL? by reflex as
their base case test. It's not too bad if you make that test
unnecessarily, in addition to the correct test, although it makes
your program harder to read. But some people checked for an empty
list as their *only* base case test. In any problem involving
trees, you have to consider leaf nodes as a base case!
* Some people used things like (NUMBER? (CAR COMPUTATION)) as the
base case test. It's possible to write a working procedure with
that approach, but it's much harder to avoid bugs, and the result
is very hard to read and understand. Perhaps you were influenced
by the fact that the domain is supposed to be lists, which is true,
but it doesn't hurt to extend the domain if that improves the
structure of the procedure. Other people thought that something
like (3)  a list of one element  could be an argument, but
the problem statement says "either a number or a list of three
elements," not "a list of either a number or three elements."
The next most common errors were data abstraction violations:
* Some people called maketree with three arguments, following the
model of the binary tree ADT in the text. This problem was about
the more general tree ADT in which a node can have any number of
children, even though in this example the nodes do have only two.
[Why would that make sense? Maybe this procedure is part of a
larger program in which we also generate expression trees from
Scheme expressions like (+ 3 4 5 6).]
* Others applied the selectors DATUM and CHILDREN to the procedure's
argument, which is *not* a tree. It's just as much a data abstraction
violation to use it when not appropriate as to notuse it when it
is appropriate.
But the worst error that came up more than once is to say one of these:
((treeify (car computation)) (treeify (cadr computation)))
'((treeify (car computation)) (treeify (cadr computation)))
instead of calling LIST. If you don't understand why that's wrong,
ask your TA to meet with you.
(b) The most common error here was to think that the domain of the
procedure should be computation lists, like the domain of TREEIFY,
instead of trees.
To make the solution clearer, I'm going to separate out the timing of
an operator as a helper procedure, although that isn't required.
(define (optime operator)
(cond ((member op '(+ )) 1)
((member op '(* /)) 5)
(else 0)))
Some students treated a datum other than one of the four operators as
an error here, which is okay, but this way makes it okay for me to call
OPTIME for a datum that turns out to be a number, which will make the
rest of the solution cleaner.
The most elegant solution uses higherorder procedures:
(define (time tree)
(accumulate +
(optime (datum tree))
(map time (children tree))))
That's it! The base case for leaves is handled implicitly by MAP.
This uses the version of ACCUMULATE on page 116 of the text.
Here's a more straightforward solution:
(define (time tree)
(if (null? (children tree))
0
(+ (optime (datum tree))
(time (car (children tree)))
(time (cadr (children tree))))))
The common errors didn't really fall into categories. Here they are:
* Trying to add a number to a list, like this:
(+ (optime (datum tree)) (map time (children tree)))
The value returned by MAP is a list, not a number, so it's not in
the domain of +. You have to use something like ACCUMULATE to add
up all the numbers in the list.
* Confusing the symbols +, , etc. with the procedures that are the
values of those variables. So for example you can say
(eq? (datum tree) '+)
but not
(eq? (datum tree) +)
* A related mistake of a different sort is to expect Scheme to evaluate
those symbols when they appear in a list, like this:
(let ((+ 1) ( 1) (* 5) (/ 5))
(+ (datum tree) ...))
Aside from the fact that the addition won't happen, because you've
changed the meaning of the symbol + so that it no longer means addition,
the value of (datum tree) is the symbol at that node, not whatever value
that symbol might have as a variable. For example, what do you expect
to be the value of this expression:
(let ((a 5))
(car '(a b c)))
The answer is A, not 5. This mistake is similar.
* A minor mistake is using EQ? to compare numbers. Use = for numbers,
EQ? for symbols.
* You can't solve a tree problem iteratively! (Strictly speaking that
isn't true; if you're really clever and perverted you can write an
iterative procedure that uses lots of extra data structures. But
nobody did that, and you can't do the naive sort of iteration that
you did try.) Solutions like
(define (time tree)
(define (timehelper tree count)
...)
(timehelper tree 0))
at best consider only one child of each branch node, and more often
lose both branches. The hallmark of tree problems is that there is
more than one recursive call in the procedure.
Scoring:
7 correct.
6 one really tiny error, or
correct except for a mistake in the base case.
5 no base case at all but otherwise correct, or
data abstraction violations in working code.
34 one part (treeify or time) works, or
both parts almost work.
12 neither works, but some understanding shown.
0 even worse.
2. Adding data abstraction.
(a) You were asked to implement the TRIAL data type, not the QUEUE data type.
(define maketrial list)
(define trialnums car)
(define trialsum cadr)
(define trialrest caddr)
Of course you can choose different names, but the implementation has to use
list, car, cadr, caddr because you are told "Each trial is a list of three
elements..."
We didn't deduct points if you *separately* implemented a queue ADT, something
like this:
(define makenewqueue list)
(define appendqueues append)
(define queuefirst car)
(define queuerest cdr)
but that wasn't required. People who tried it generally failed to notice
that the two places in ADDUP that create queues do it differently, so two
constructors are needed.
What we DID deduct for is a mixed type, a queueoftrials, like this:
(define trialnums caar) ; wrong!
(define trialsum cadar)
(define trialrest caddar)
That was the most common error. Two others that came up in several papers:
* Moving some of the algorithm of ADDUP into the constructor, like this:
(define (maketrial queue) ; wrong!
(map (lambda (new)
(list (cons new (caar queue))
(+ new (cadar queue))
(remove new (caddar queue))))
(caddar queue)))
* A really really bad error was to chop random pieces of code out of ADDUP
and try to use them out of context, like this:
(define queue (list trial)) ; very wrong!
(define trial (car queue))
Where do you think your definition of QUEUE finds a value for TRIAL?
These alleged constructors and selectors aren't even procedures. We
gave zero points to any solution that included things like this.
(b) Rewriting ADDUP.
Since you were given such a narrow task, rewriting existing procedures to
use the trial ADT, there is only one possible correct solution:
(define (addup nums goal)
(adduphelper (list (MAKETRIAL '() 0 nums)) goal))
(define (adduphelper queue goal)
(cond ((null? queue) #f)
((eq? (TRIALSUM (car queue)) goal) (TRIALNUMS (car queue)))
(else (adduphelper
(append (cdr queue)
(map (lambda (new)
(MAKETRIAL (cons new (TRIALNUMS (car queue)))
(+ new (TRIALSUM (car queue)))
(remove new (TRIALREST (car queue)))))
(TRIALREST (car queue))))
goal))))
The invocations of the new constructor (twice) and of the new selectors
(six times) are capitalized above.
There were three common kinds of errors here:
* missing some of the changes
* not using (car queue) as the argument to the selectors
* using the new constructor or selectors where inappropriate
A less common error was to insert the names of selectors in the code
but not invoke them, or invoke them with no argument at all.
By the way, we made an error in the original procedure; we should have
used = rather than EQ? in the second COND clause.
Scoring: Two points off for each of the following:
* part (a): bad ADT
* part (b): missing some of the changes
* part (b): not using (car queue) as the argument to the selectors
* part (b): using the new constructor or selectors where inappropriate
Anything worse than that got zero. In some cases we took off an odd
number of points if two errors seemed related in a way that made it seem
unfair to subtract two points for each one.
3. Datadirected disassembler
(define (assembly instruction)
(let ((op (listref ops (car instruction))))
(printer (cons (car op) (cdr instruction))
(cadr op))))
You don't have to use the LET (instead calling listref twice) but
really there is no other good solution. We allowed NTH in place of
LISTREF, but you should really learn LISTREF, which is the Scheme
standard for selecting an element from a list.
The crucial point is that ASSEMBLY is datadirected in the sense that
it looks up the opcode in the table OPS instead of checking explicitly
for each possibility. (PRINTER is also datadirected in that it uses
the information from OPS to determine the order in which operands
are printed, but you didn't have to write that part.)
For the most part people either got the point or didn't. There were
a few minor errors, e.g., LIST instead of CONS or CDR instead of CADR.
The most common major error was to think that because the problem says
"data directed" it has to use PUT and GET.
Scoring:
3 correct
2 has the idea
1 has an idea
0 other
4. Box & pointer diagrams
> (append '(a b) '())
(A B)
>XX>X/
 
V V
A B
The empty list has no elements, so it doesn't contribute anything
to the APPEND.
> (cons '(a b) '())
((A B))
>X/

V
XX>X/
 
V V
A B
The pair at the top, to which the initial arrow points, is the one
created by the CONS. There are two ways to think about this:
(1) CONS adds one new element at the front of an existing list.
In this case, the existing list was empty, so CONS creates a
oneelement list. (2) CONS always creates exactly one pair,
whose car and cdr are the two arguments. In this case the
car is (A B) and the cdr is the empty list.
A few people got that part wrong because they showed the printed
result in dotted form: ((a b) . ()). Scheme never prints a dot
followed by an open parenthesis! It uses list notation instead.
> (list '(a b) '())
((A B) ())
>XX>//

V
XX>X/
 
V V
A B
The two pairs in the top row are the ones generated by LIST. It
always creates a list whose length is the number of arguments,
which is two in this example. The first element is (A B); the
second is the empty list. That second pair has a slash in both
boxes; the slash in the car means that the empty list is an
element; the slash in the cdr means that this is the end of the
toplevel list.
We did accept notations such as
... >X/

V
/
but in fact there's no reason to denote an empty list in the
car of a pair differently from an empty list in the cdr!
> (caadr '((1 2) (3 4)))
3
The "box and pointer diagram" is also just 3 in this trivial case,
since there are no pairs in the result.
(cdr '((1 2) (3 4))) > ((3 4))
(car '((3 4))) > (3 4)
(car '(3 4)) > 3
Scoring: one point each. No more than one point off for leaving
the initial arrow out of all the diagrams.

If you don't like your grade, first check these solutions. If we
graded your paper according to the standards shown here, and you
think the standards were wrong, too bad  we're not going to grade
you differently from everyone else. If you think your paper was
not graded according to these standards, bring it to Brian or your TA.
We will regrade the entire exam carefully; we may find errors that
we missed the first time around. :)
If you believe our solutions are incorrect, we'll be happy to discuss
it, but you're probably wrong!