CS 61A		Fall 1998		Midterm 2 solutions

1.  Box & pointer diagrams

> (append (list 'a 'b) '(c d))

(A B C D)

--->XX----->XX----->XX----->X/
    |       |       |       |
    V       V       V       V
    A       B       C       D

Most people got this.  The most common problem was to put quotation marks
in the answer, in the printed result and/or in the diagram.  The quotation
marks are part of Scheme expressions, but not part of the value of those
expressions!  In other words, the value of the expression 'A is just A,
not 'A.

> (cons (list 'a 'b) (cons 'c 'd))

((A B) C . D)

--->XX------------->XX--->D
    |               |
    V               V
    XX----->X/      C
    |       |
    V       V
    A       B

The pair at the top, to which the initial arrow points, is the one
created by the CONS. 

This was the part most commonly answered incorrectly.  The least bad wrong
answer was ((A B) . (C . D)).  This is close to correct, in that if you
quoted it to Scheme, you'd get this data structure.  But Scheme never prints
a dot followed by an open parenthesis!  It uses list notation instead.
(In this case it's an "improper list" because it doesn't end with an empty
list in the last cdr.)  Other wrong answers were ((A B) C D), which would be
a proper list with an extra pair, as if the problem had been
	(cons (list 'a 'b) (LIST 'c 'd))
and (A B C . D), a structure of only three pairs, as if the problem had been
	(APPEND (list 'a 'b) (cons 'c 'd))


> (list (list 'a 'b) (append '(c) '(d)))

((A B) (C D))

--->XX------------->X/
    |               |
    V               V
    XX----->X/      XX----->X/  
    |       |       |       |
    V       V       V       V
    A       B       C       D

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 (C D).


> (cdar '((1 2) (3 4)))

(2)

--->X/
    |
    V
    2

(car '((1 2) (3 4)))  -->  (1 2)
(cdr '(1 2))          -->  (2)

Scoring: 1/2 point per printed form, 1/2 point per box and pointer diagram,
rounded down to the nearest point.  Exception: Side-issue mistakes made
consistently in all problems, such as putting quotation marks in the result,
lost no more than 1 point altogether in the printed form and 1 point
altogether in the diagram.

Note:  When drawing box and pointer diagrams, please be careful about
the arrows; it makes your diagrams much easier to read.  There should
be an arrowhead at the end (next to the thing the arrow points at).
The tail of the arrow should be INSIDE a box; the head should be
NEXT TO a box or other datum.  For example:

      +-----+-----+
      |     |    /|
----->|  |  |  /  |
      |  |  |/    |
      +--|--+-----+
         |
         V

         2

Note how the arrow that points to the 2 starts inside the car of the pair.


2.  Using data abstraction.

(a) assoc

(define (assoc key a-list)
  (cond ((NULL? a-list) #f)
	((equal? key (ASSOCIATION-KEY (CAR a-list))) (CAR a-list))
	(else (assoc key (CDR a-list)))))

(b) index and index-one

(define (index groups)
  (if (NULL? groups)
      '()
      (append (index-one (CAR groups)) (index (CDR groups)))))

(define (index-one group)
  (define (help groupname people)
    (if (EMPTY? people)
	'()
	(CONS (MAKE-ASSOCIATION (FIRST people) groupname)
	      (help groupname (BF people)))))
  (help (ASSOCIATION-KEY group) (ASSOCIATION-VALUE group)))

There are 15 procedure calls in capital letters above.  These are the
candidates for changes to respect data abstraction: the selectors, the
constructors, and the empty tests.

As the exam said (in boldface!), an association *list* is not an
association, but merely a sequence.  Therefore, the procedures that
manipulate the variable a-list are unchanged; they remain CAR, CDR,
CONS, and NULL? in the solution.

On the other hand, the values of (car a-list) and group are associations,
and so we use the selectors ASSOCIATION-KEY and ASSOCIATION-VALUE to
examine their components.  Also, in index-one, we are constructing
an association list by CONSing a new association, made with the constructor
MAKE-ASSOCIATION, onto the result of a recursive call to help.

Finally, in this particular association list, the value part of each
association is a *sentence* of names of people, and so we use FIRST, BF
(or BUTFIRST), and EMPTY? to examine the value of the variable people.

Scoring:  We first scored this question on a scale of 15 "little points,"
giving one point for each of the 15 capital-letter names in the above
solution that you had correct.  We then subtracted two little points for
any other change you made to the given code, except that you lost at most
three little points for correctly using a new abstract data type that you
invented.  (For example, several people invented one for sequences of
associations.)  We then converted to a 0-5 scale as follows:

	5   14-15
	4   11-13
	3   8-10
	2   5-7
	1   2-4
	0   0-1

The most common unnecessary change, other than inventing a new ADT, was
the following modification to assoc:

(define (assoc key a-list)	;; wrong
  (cond ((null? a-list) #f)
	((equal? key (association-key (car a-list)))
	 (MAKE-ASSOCIATION (ASSOCIATION-KEY (CAR A-LIST))
			   (ASSOCIATION-VALUE (CAR A-LIST))))
	(else (assoc key (cdr a-list)))))

Respecting a data abstraction doesn't mean you have to reconstruct a
perfectly good association!  Perhaps people thought that the word
"association" had to appear somewhere in order to respect the
abstraction, but it doesn't.


3.  typed calculator

The solution to (a) is a subset of the solution to (b); we divided it
into two parts because when I tried out the exam on the TAs they thought
it was too many details to read all at once, so it'd be easier this way.
So here's the complete solution, with the part added for (b) in capitals:

(define (times a b)
  (attach-tag (cond ((equal? (type-tag a) (type-tag b))
		     (word 'sq- (type-tag a)))
		    ((GET (TYPE-TAG A) (TYPE-TAG B)))
		    ((GET (TYPE-TAG B) (TYPE-TAG A)))
		    (else (word (type-tag a) '- (type-tag b))))
	      (* (contents a) (contents b))))

This terse solution takes advantage of the fact that a COND clause can
have a single expression, in which case if the value of the expression
is anything other than #F, that's what COND returns.

Most people gave longer, but perfectly okay, solutions because you didn't
think to use the COND as the first argument to ATTACH-TAG, but instead
said (DEFINE (TIMES A B) (COND ...)) and had four separate calls to
ATTACH-TAG.  Some people used a LET to avoid some of the repetition.

Since the types are symbols, it's okay to use EQ? instead of EQUAL?.

Scoring:

5  Correct
4  DAVs, trivial mistakes, or forgetting the second GET for reverse order
3  Uses GET correctly but has other significant errors
2  Part (a) correct
1  Domain and range correct, but wrong results
0  Even worse

One common small mistake was to invent your own ADT for type-tagged data
instead of using the one provided in the book.

Another too-common mistake was to put quotation marks on the arguments
to GET:  (get '(type-tag a) '(type-tag b)).  I assume this means that
some students have taught themselves a mystical formula saying "always
quote the arguments to GET."  Clearly such students don't understand
what quotation means, which is sad this late in the semester.

But there were two common mistakes that were even worse.  One was to use
DISPLAY or some other printing procedure to attempt to assemble the
type tag for the result:

	(display (type-tag a))	;; wrong wrong wrong!!!
	(display '-)
	(display (type-tag b))

I don't know whether these students just forgot about WORD or were
afraid that using it would be a data abstraction violation, but using
DISPLAY is much, much worse than any DAV.  The problem is that printing
something on the screen is not the same as returning a result!  Suppose
you say

	(let ((result (times some-value some-other-value)))
	  (times result result))

This is supposed to work; the result from TIMES should be usable as
part of a larger computation.  But if you just print that result, instead
of returning it, you can't use it in this way.  Composition of functions
is one of the most important ideas in this course.

The other really awful mistake was to build specific examples into
the program, as in

	(if (equal? (type-tag a) 'volt) ...)	;; wrong wrong wrong!!!

It's *always* bad to build a specific example into a solution.  But it's
especially bad when the whole point of the problem is to use data-directed
programming, which means precisely that the details of the algorithm are
embodied in a data structure rather than in the program itself.


4.  deep-accumulate

Here's the solution I was hoping for:

(define (deep-accumulate op init struct)
  (cond ((null? struct) init)
	((not (pair? struct)) struct)
	(else (op (deep-accumulate op init (car struct))
		  (deep-accumulate op init (cdr struct))))))

Many other correct solutions are possible.  One variant, for people who
didn't quite have the courage to use a single value as the base case,
was to replace the second COND clause with this:

	((not (pair? (car struct)))
	 (op (car struct)
	     (deep-accumulate op init (cdr struct))))

Also, instead of using car/cdr recursion, you could replace the last
COND clause with this:

	(else (accumulate op
			  init
			  (map (lambda (s) (deep-accumulate op init s))
			       struct)))

but most people who tried this got it wrong, because they tried to map
deep-accumulate itself instead of using a LAMBDA as above.

Another clever solution was to use the FRINGE procedure from exercise 2.28
to turn the deep list into a flat list of atoms:

(define (deep-accumulate op init struct)
  (accumulate op init (fringe struct)))

To test for a leaf of the structure, we accepted ATOM? and NUMBER? in place
of (NOT (PAIR? STRUCT)) even though there's no ATOM? in the current version
of Scheme, and nothing in the problem restricts the elements to numbers.

One common error was to use the Tree abstract data type (with selectors
DATUM and CHILDREN) although this problem is not about those Trees.  People
who did that may have been copying a solution from an earlier year's exam.

Another too-common error was to build the operation + or the identity
element 0 into the code; this isn't having the idea, which is about
higher-order functions.

Scoring: The possible answers to this were too varied for us to make up a
detailed enumeration of them.  Instead we used my standard grading scale
for programming questions:

5    correct
3-4  has the idea
1-2  has an idea
0    other

-----------------------------------

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!