CS 61A		Fall 2000		Midterm 2 solutions

1.  Skittles in OOP.

(a)  Since methods to read local state variables are automatically provided,
all we need is

	(define-class (skittle color))

We didn't take off for explicitly providing a COLOR method, unless the method
was so convoluted that it actually wouldn't work.  But learn to do things
simply instead of making your programs unnecessarily complicated.

Scoring:  One point if correct.


(b)  There were two basic approaches, one keeping minimal state information
and one keeping extra redundant information to avoid writing some methods.
I prefer the first approach:

(define-class (skittle-bag)
  (instance-vars (bag '()))
  (method (add skit)
    (set! bag (cons skit bag)))
  (method (count)
    (length bag))
  (method (colors)
    (map (lambda (s) (ask s 'color)) bag))
  (method (remove)
    (let ((result (car bag)))
      (set! bag (cdr bag))
      result)))

Note that the REMOVE method must first remember the to-be-returned
skittle, then remove it from the list, and then--last of all--return
the result.  This can't be done without LET or some equivalent
mechanism to hold the removed skittle.

	(method (remove)	;; wrong!!
	  (car bag)
	  (set! bag (cdr bag)))

The second approach remembers the colors and count in state variables
as well as the actual skittles:

(define-class (skittle-bag)
  (instance-vars (bag '()) (count 0) (colors '()))
  (method (add skit)
    (set! bag (cons skit bag))
    (set! count (+ count 1))
    (set! colors (cons (ask skit 'color) bag)))
  (method (remove)
    (let ((result (car bag)))
      (set! bag (cdr bag))
      (set! count (- count 1))
      (set! colors (cdr colors))
      result)))

This is okay, and got full credit.  And it has the virtue that its
(implicit) COLOR method is Theta(1) time instead of Theta(N) time
because it doesn't have to count the length of the BAG list, although
there is a slight slowdown of the ADD and REMOVE methods.  But it has
the disadvantage that keeping redundant information increases the
possibility of program bugs.  In this simple problem it's unlikely
to happen, but what if your ADD or REMOVE method updated some of the
three state variables but not others?  This could be a difficult bug
to find.  (But don't make a religion of this; I'd use redundant
information if there were a huge difference in efficiency.)

We didn't give full credit to solutions that kept *only* a list of
colors and not a list of skittle objects.  Because skittles have such
simple behavior, and no changing local state, such programs could have
the correct apparent results, if the REMOVE method instantiates a new
skittle of the removed color.  (In this simple program, two yellow
skittles can't really be distinguished, so making a new one isn't
visibly different from returning the same one originally added.)  But
these solutions violate the spirit of simulations with objects, and we'll
see that two same-color skittles actually *can* be distinguished if we
try hard enough.

Scoring: 3 if correct, 2 for minor errors, 1 for major errors, 0 for
very serious errors.

The only common 2-point solution was storing only a list of colors.
Other 2-point solutions were generally forgetfulness, such as keeping
redundant information and not quite updating everything in either ADD
or REMOVE.


Common 1-point solutions:

	(parent (skittle)) or (parent (skittle color)).  A skittle-bag
	is not a kind of skittle!  It doesn't have the same behavior as
	a skittle; in particular, it doesn't have a color.

	COLORS method returns a list of skittles instead of a list
	of colors.

	Some method entirely missing.

	REMOVE returns something other than a skittle (usually a color).

	REMOVE returns the wrong skittle for lack of the LET or an
	equivalent.  (We accepted solutions that used another instance
	variable as a temporary holder for the returned skittle, although
	that's not an elegant solution.  Try not to keep state variables
	if temporary variables would do the job.)

	Class variables instead of instance variables.

	Results from COLORS or REMOVE are printed (using DISPLAY) instead
	of being returned.  (We didn't take off if the results are both
	printed and returned.  But please cure yourselves of that habit!
	It's hardly ever the right thing to print something in a procedure.)

	Bad domain or range of some method.

	Misuse of MAP in the COLORS method, usually by having a first
	argument that isn't a function, such as
		(map (ask self 'color) bag)	;; wrong!
		(map color bag)			;; wrong!


2.  Leaf depths of binary tree

(define (leaf-depths tree)
  (define (help tree depth)
    (cond ((null? tree) '())
	  ((leaf? tree) (LIST DEPTH))
	  (else (APPEND (HELP (LEFT-BRANCH TREE) (+ DEPTH 1))
			(HELP (RIGHT-BRANCH TREE) (+ DEPTH 1))))))
  (help tree 0))

The key to this problem is remembering the range of the function: it's
supposed to return a list of numbers.  Therefore, even in the base cases
it has to return a list!  A common wrong answer was
	((null? tree) 0)	;; wrong!
which can't be right because it returns a number, not a list.  Similarly,
	((leaf? tree) depth)	;; wrong!
is plausible if you forget about the range, but wrong because it doesn't
return a list.

Since the two recursive calls return lists of numbers, and we want the
overall result to be a list of numbers, the combiner has to be APPEND.
Either CONS or LIST would return a list-of-lists.

Scoring: 3 if correct, 2 if minor errors, 1 if major errors, 0 if
not tree recursive.

Common 2-point errors:

	Base case(s) wrong.

	CONS or LIST instead of APPEND.

	Data abstraction violation (CADR and CADDR instead of LEFT-BRANCH
	and RIGHT-BRANCH).

Common 1-point errors:

	Tree recursion that calls LEAF-DEPTHS instead of HELP.

	Recursion on (CAR TREE) and (CDR TREE).  Note that this isn't
	just a DAV; it gives incorrect results!

	Recursion on (ENTRY TREE) as well as the two branches.

	Function returns a number instead of a list of numbers
	(e.g., using + instead of APPEND).

The only common 0-point solutions have only one recursive call instead of two.


3.  Left-only nodes of binary trees.

The key point here is that this is a tree recursion; both left and
right branches of each node must be checked.

The most elegant solutions take advantage of a (NULL? TREE) base case
to avoid having to make a lot of checks for special cases:

(define (left-only tree)
  (if (null? tree)
      0
      (+ (left-only (left-branch tree))
	 (left-only (right-branch tree))
	 (if (and (not (null? (left-branch tree)))
		  (null? (right-branch tree)))
	     1
	     0))))

In other words, the total number of left-only nodes in this tree is the number
found in the left child, plus the number found in the right child, plus maybe
1 for this node itself, if it's a left-only node.

Other solutions are okay too; for example:

(define (left-only tree)
  (cond ((null? tree) 0)
	((leaf? tree) 0)
	((null? (right-branch tree))	; see discussion below
	 (+ 1 (left-only (left-branch tree))))
	(else (+ (left-only (left-branch tree))
		 (left-only (right-branch tree))))))

Note that the third COND clause doesn't have to check
	 (and (not (null? (left-branch tree)))
	      (null? (right-branch tree)))
because the second COND clause has already established that this isn't
a leaf node, so the two branches can't both be null -- which is what it
means to be a leaf node.  So if the right branch is null, we know that
the left branch isn't.

Note also that the third COND clause must include a recursion for the
right branch; a common error was just to return 1 in this situation.

A tree recursive problem can't be solved iteratively!  [Actually this isn't
quite true, but a correct iterative solution requires essentially simulating
tree recursion by maintaining an explicit list of not-yet-visited nodes
and nobody even tried it.]  The typical attempts at iterative helper
procedures were actually mixtures of iteration (when a left-only node is
found) and tree recursion (for a node with both children non-null).  The
result was something like
	(+ (helper (left-branch tree) result)	;; wrong!
	   (helper (right-branch tree) result))
If the value of RESULT is nonzero at this call, because some node higher
in the tree was left-only, then that value is counted twice in the overall
total, so the value returned would be too large.

Another way to go wrong was to ignore the range of the procedure, returning
a number in some cases and a list (of numbers or of nodes) in other cases.

Scoring: 4 if correct.  3 for minor errors, such as a bad or missing base
case.  2 for serious algorithm errors (including the semi-iterative programs
and the failure to recur for the left child of a left-only node mentioned
above).  1 for CAR/CDR recursion instead of LEFT-BRANCH/RIGHT-BRANCH and
similar serious misunderstandings of the problem.  0 for a solution without
tree recursion or other incoherent attempts.


4.  Dyadic operations in message-passing style.

There is an asymmetry in the solution, since the two operands of the
addition are accessed differently.  The first one is represented by the
very procedure we're writing -- in OOP notation it would be SELF -- while
the second one is an argument to the method we must return.

((eq? op 'add)
 (lambda (num2)
   (make-from-real-imag (+ x (num2 'real-part))
			(+ y (num2 'imag-part)))))

It's also fine to say (real-part num2) and (imag-part num2).

A noteworthy common error was
	(add-complex x y)	;; wrong!
X and Y are real numbers, not complex numbers.  They are the real part
and the imaginary part of a single complex number.

Other common errors were to confuse this representation with one of the
others we've seen recently, either OOP or tagged-data.  Solutions using
ASK or TYPE-TAG got at most 2 points.

Scoring:  4 if correct.  3 for small mistakes, such as thinking there is
a variable NUM1 whose value is a complex number, instead of using the
real values X and Y.  2 for solutions with serious errors but returning
a procedure with the correct domain (a complex number) and range (also a
complex number).  That is, a 2-point-or-more solution must start
	(lambda (num2) (make-from-real-imag ...))
1 point for a solution that returns a procedure, but with the wrong
domain or range.  Common 1-point solutions were
	(lambda (x y) ...)	    ;; wrong!
	(lambda (num2) (cons ...))  ;; wrong!
0 points for solutions not returning a procedure.


5.  Data directed function composition.

(a) The most elegant solutions used the helper procedure COMPOSE:

(define (function name)
  (if (empty? name)
      (lambda (x) x)
      (compose (get (first name) 'function)
	       (function (bf name)))))

(define (compose f g)
  (lambda (x) (f (g x))))

Solutions not using COMPOSE had to do the composition inside FUNCTION,
which is a little tricky:

(define (function name)
  (if (empty? name)
      (lambda (x) x)
      (lambda (x) ((get (first name) 'function) ((function (bf name)) x)))))

Note the double open parentheses at ((GET... and ((FUNCTION...  These are
necessary because the calls to GET and FUNCTION return functions, which we
then must invoke.

It's also okay to move the LAMBDA outside the IF, since both branches of
the IF return a function of X:

(define (function name)
  (lambda (x)
    (if (empty? name)
	x
	((get (first name) 'function) ((function (bf name)) x)))))

The decomposition of the name can be done right-to-left instead of
left-to-right, by reversing the order of the GET and FUNCTION calls:

(define (function name)
  (if (empty? name)
      (lambda (x) x)
      (compose (function (butlast name))
	       (get (last name) 'function))))

or equivalently for the other solutions above.

Finally, it's possible to make this an iteration, but that generally requires
reversing the left-to-right order:

(define (function name)
  (define (helper name fn)
    (if (empty? name)
	fn
	(helper (butlast name) (compose (get (last name) 'function) fn))))
  (helper name (lambda (x) x)))

In any of these solutions, the base case could be a one-letter name instead
of an empty name, but that's less elegant:

(define (function name)
  (if (empty? (butlast name))
      (get (last name) 'function)
      (compose (function (butlast name))
	       (get (last name) 'function))))

I think it's better to learn to try empty, zero, leaf, etc. as a base case
first. Only rarely do you have to use one-letter, one, parent-of-leaf, etc.

Scoring:  3 if correct.  2 for base case errors or composing the functions
backwards (doing CADR instead of CDAR, etc.).  1 for an incorrect composition,
usually calling one function with the other as argument:
	((get (first name) 'function) (function (butfirst name)))  ;; wrong!
0 points for not even trying to compose the functions, no recursion at all,
or non-data-directed solutions, such as procedures with the cases A, D, S,
M, and I built in.


(b) Handling C and R

These letters add nothing to our understanding of what function to use, so
we should ignore them by making them call the identity function:

(put 'c 'function (lambda (x) x))
(put 'r 'function (lambda (x) x))

Scoring: One point if right!

A fairly common error was (lambda (x) (x)).

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

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!