path: root/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm2/mt2-1.soln.txt

CS 61A          Solutions to sample midterm 2 #1

1.  What will Scheme print?

Note: Please draw actual boxes, as in the book and the lectures, not XX and X/
as in these ASCII-art solutions.

Also, please put in the start arrows!  Sometimes it's hard to know where your
diagrams are supposed to begin, especially if you use leftward and upward
pointing arrows.

> (map caddr '((2 3 5) (7 11 13) (17 19)))
ERROR

	(caddr '(2 3 5)) is 5; (caddr '(7 11 13)) is 13.  But (17 19)
	doesn't have a caddr, which would be the third element of a
	two-element list.  The error is attempting to take the car of
	the empty list.

	The most common wrong answer was (5 13), thinking that the error
	would just slide under the rug.

> (list (cons 2 (cons 3 5)))
((2 3 . 5))


--->X/
    | 
    XX--->XX---> 5
    |     |
    V     V
    2     3

	There were two points to note in this problem:  (cons 3 5) creates
	an improper list, and LIST is called with one argument, making a
	one-element list (whose spine is the topmost pair in the diagram).

	One error was to think that every call to CONS results in something
	that prints with a dot, like this: ((2 . (3 . 5)))  But in fact
	Scheme never prints a dot if the cdr is a pair; if the ultimate
	pair of a chain of cdr-linked pairs doesn't have the empty list as
	its cdr, you get the improper list notation (2 3 . 5)

	The extra parentheses in the printed form show that the result is
	a one-element list whose element is a list structure (in this case,
	an improper list rather than an actual list).


> (append (list '(2) '(3)) (cons '(4) '(5)))
((2) (3) (4) 5)


--->XX--->XX--->XX--->X/
    |     |     |     |
    V     V     V     V
    X/    X/    X/    5
    |     |     |     
    V     V     V     
    2     3     4    

	The most problematic part of this for most students was the CONS.
	Some people, remembering that the arguments to APPEND must be
	lists, said that this produced an error -- but of course CONS can
	produce a list, if its second argument is a list, as it is here.
	[Fine print: In fact the *last* argument to APPEND is *not* required
	to be a list, although the others are.  See the Scheme reference
	manual.]  In this case, the CONS call produces the list ((4) 5).
	The asymmetry in the handling of (4) and (5) comes from the meaning
	of CONS in creating a list: the first argument, the car of the new
	pair, is an *element* of the resulting list, whereas the second
	argument, the cdr of the new pair, is a *sublist* of the resulting
	list.  If this confuses you, think about what you'd expect
			(cons 4 '(5))
	to do.

	The most common error, still about the CONS call, was to see that
	it has to do something different from the LIST call, but still
	try to make it treat its arguments symmetrically, resulting in
	the wrong answer ((2) (3) 4 5).


> (list (cons '(0) '(1)) (append '(2) '(3)))
(((0) 1) (2 3))

--->XX------------->X/
    |               |
    V               V
    XX--->X/        XX--->X/
    |     |         |     |
    V     V         V     V
    X/    1         2     3
    |
    V
    0

	LIST returns a list with as many elements as it has arguments -- in
	this case, two elements.  The top two pairs in the diagram are the
	ones generated by LIST.

	CONS generates exactly one new pair.  In this problem, the first pair
	on the second line of the diagram is the one generated by CONS.  Its
	car is the pair on the third line, which is the list (0); its cdr is
	the second pair on the second line, which is the list (1).  The
	important thing to see here is that the lists (0) and (1) do not play
	similar roles in the result, because of the way lists are defined.
	The car of a pair is a list *element*; the cdr of the same pair is a
	*sublist*.  So the value returned by the CONS invocation is a list of
	two elements, namely (0) and 1 -- not (0) and (1); not 0 and 1.

	APPEND strings together the elements of its arguments, so in this
	case, the result of the APPEND invocation is the list (2 3).

There were two common wrong answers to this part.  One mistake was to put
the last element of a sublist in the cdr of a pair, like this:

--->XX------------->X/		; WRONG!
    |               |
    V               V
    XX--->1         XX--->3
    |               |  
    V               V  
    X/              2  
    |
    V
    0

The numbers 1 and 3 are attached to the cdrs of their parent pairs,
rather than to the cars.

The other common mistake was to leave out the pair just above the zero,
like this:

--->XX------------->X/          ; WRONG!
    |               |
    V               V
    XX--->X/        XX--->X/
    |     |         |     |
    V     V         V     V
    0     1         2     3

A less common, but more serious, error was to leave out part of the
work by having parentheses in the diagram:

--->XX------------->X/          ; WRONG!
    |               |
    V               V
    XX--->(1)       XX--->(3)
    |               |
    V               V
    (0)             2

There are never any parentheses in a box and pointer diagram.  The
parentheses in the *printed representation* of a list structure are
just a notation to represent *pairs* in the actual structure.


Scoring:  One point for each printed result; one point for each diagram,
except for the first part, which got two points or none.


2.  Binary search trees

Although the ADT doesn't include empty trees, the program is easier to
write if you allow for the possibility of getting an empty list as
argument instead of a tree, because that's what happens when you try to
recur for the children of a leaf node.  On that assumption, here's one
way to write it:

(define (all-smaller? tree num)
  (or (null? tree)
      (and (< (entry tree) num)
	   (all-smaller? (left-branch tree) num)
	   (all-smaller? (right-branch tree) num))))

(define (bst? tree)
  (or (null? tree)
      (and (all-smaller? (left-branch tree) (entry tree))
	   (all-larger? (right-branch tree) (entry tree))
	   (bst? (left-branch tree))
	   (bst? (right-branch tree)))))

Most people wrote equivalent programs using COND, which is fine, but I
find this style cleaner when writing predicates.

A BINARY TREE is just a tree in which each node has at most two
children.  A BINARY SEARCH TREE is a binary tree with the ordering
constraints as described in the text.  The text doesn't make that
entirely clear, because their only use of binary trees is to represent
the SET ADT, for which a BST is needed.  Therefore, we didn't take off
points if in part (a) you assumed the ordering relationship and therefore
only checked the right branch of the tree, as long as you did the tree
recursion properly in (b).

Scoring:  This and the remaining problems are graded on the scale
		5    correct
		3-4  has the idea
		1-2  has an idea
		0    other

Having the idea, in this problem, means doing a tree recursion.  The most
common form of not having the idea was to think, in part (b), that the
ordering must be checked only with respect to the root node, so you left
out the recursive calls to BST?.

We took off one point if you violated the binary tree ADT, using CAR and
CDR instead of ENTRY, LEFT-BRANCH, and RIGHT-BRANCH.  (If you thought
that those three things are names of trees, rather than of procedures,
you didn't have the idea.)

A too-common error was to say things like
	(< (left-branch tree) (entry tree))
as if the left branch were a number!  It's not; it's a tree.


3.  Tree fanout.

The best answer is

(define (max-fanout tree)
  (accumulate max
	      (length (children tree))
	      (map max-fanout (children tree))))

This takes advantage of the fact that ACCUMULATE requires a starting value
for the accumulation, usually 0 or 1 in the book's examples, but we can use
the fanout of this node as the starting value.

Here's the non-higher-order, mutual-recursion version:

(define (max-fanout tree)
  (max (length (children tree))
       (max-fanout-forest (children tree))))

(define (max-fanout-forest forest)
  (if (null? forest)
      0
      (max (max-fanout (car forest))
	   (max-fanout-forest (cdr forest)))))

Some people made this more complicated by using a one-element forest as
the base case in max-fanout-forest, thereby requiring that max-fanout
check for the special case of a leaf node.  If this were a general
problem about accumulating the MAX of arbitrary numbers, we couldn't use
0 as the base case, because all the numbers might be negative, so if
anything the base case would have to be negative infinity.  But here
the numbers are node fanouts, and there's no such thing as a negative
number of children!

Note that max-fanout does not need a base case.  The recursion happens
either in MAP, for the first solution, or in MAX-FANOUT-FOREST, for
the second solution.

Having the idea, in this problem, mostly meant understanding the Tree ADT.
The totally wrong solutions were ones that applied CAR and CDR to a Tree --
or, equivalently, the ones that said DATUM and CHILDREN but meant CAR and
CDR.  Note that there is no reference to DATUM in a correct solution to
this problem!  The fanout has nothing to do with the values in the nodes,
only with the Tree's shape.

Not only is CAR/CDR recursion a data abstraction violation, it's also a
fundamental misunderstanding of this particular problem.  It's often the
case that similar problems could be posed for abstract Trees and for
list structures viewed as trees.  But if you use CAR/CDR recursion, you
are thinking of each pair as a node in a binary tree, essentially, so
the fanout is always 2!  The whole issue of fanout doesn't arise unless
you have real Trees to think about.

CAR/CDR programs, or their equivalent -- such as programs with expressions
of the form (not (pair? tree)) -- got at most 2 points, but more often 0 or 1.
So did programs that confused trees with forests.

Some not-so-bad programs tried to apply MAX to a list of lists of numbers,
rather than to a list of numbers.  Our general rule was that if we could
fix your program by replacing a call to MAP with a call to FLATMAP, it
got 3 points.

A common problem, not so bad, was to get confused about the domain of MAX.
This procedure takes numbers as arguments, not lists; you can't say
        (max '(1 2 3 4))
but you *can* say
        (apply max '(1 2 3 4))
or in this case, because all the numbers are positive,
        (accumulate max 0 '(1 2 3 4))
The advantage of ACCUMULATE over APPLY is that in some cases, people who
used APPLY ended up applying MAX to an empty list -- in other words, trying
to call MAX with no arguments.  That's not allowed, but ACCUMULATE always
calls MAX with exactly two arguments, if at all, so it doesn't have the
same potential bug.  All problems in this category lost only one point.

The comments in the solution to question 2 about making unnecessary data
structures apply here, too.  Several people made trees in which the datum
of each node was replaced by its fanout.  Others made linear sequences of
tree nodes.  All of these things only complicate the program; whatever you
end up doing to create the structure and then process it could instead
solve the problem directly in one step.

Scoring:  3 or more points for a solution that uses the Tree ADT correctly
and actually computes fanouts and maximums.  2 or fewer points for a solution
with car/cdr recursion, tree/forest confusion, nothing about fanouts, or
nothing about maximum.


4.  Data-directed programming.

(define (plus x y)
  (let ((tx (type x))
	(ty (type y)))
    (if (eq? tx ty)
	(attach-tag tx (+ (contents x) (contents y)))
	(let ((gxy (get tx ty))
	      (gyx (get ty tx)))
	  (cond ((number? gxy)
		 (attach-tag ty (+ (* gxy (contents x)) (contents y))))
		((number? gyx)
		 (attach-tag tx (+ (contents x) (* gyx (contents y)))))
		(else (error "You can't add apples and oranges.")))))))


The use of LET in this solution isn't essential; various rearrangements
are possible and are equally good.

Surprising numbers of people had trouble understanding what the problem
was asking for.  They wrote programs in which 3 dynes PLUS 4 centimeters
equals 12 ergs!  Sorry, 3 plus 4 is not 12 no matter how clever your
coding style is.  As the problem clearly stated, you were asked to write
one procedure, the addition procedure, for a larger project that would
also include a multiplication procedure when completed.  Moral: don't
be in such a hurry to write code.  Make sure you understand the problem
you are being asked to solve first!

Another common way to get in trouble was to try to apply the number you
found in the table (12, in the example) as a procedure.  Just because
there is an example in the book in which a table contains procedures as
entries, that doesn't mean that every table has to contain procedures!
This particular table contains numbers, for units that can be added
together, and symbols, for units that can be multiplied.

Scoring: 8 points for a perfect solution.
	 4-7 points for a flawed solution not grossly confused.
	 2-3 points for a grossly confused but not clueless solution.
	 0-1 point for a solution showing no understanding at all.

In general we subtracted two points for each flaw, down to the
minimum for the categories as indicated.  Here are some 2-point errors
that bottomed at 4 points:

-- not checking the number? predicate
-- not checking for the arguments being backwards in the table
-- incorrect conversion formula
-- violation of the attach-tag data abstraction
-- wrong args to GET

Here are some errors eligible for the 2-3 point range:

-- checking explicitly for 'ft or 'in
-- applying a non-procedure
-- Lisp syntax errors like non-symbol formal parameters


5.  OOP

The central point of this question is that in the OOP paradigm, objects are
used for everything, and the structure of the object classes reflects the
structure of the real-world situation being simulated.

(a) parenthood

The class VANILLA has the class SCOOP as its parent, because a vanilla scoop
is a particular kind of scoop.

Is a scoop a special kind of cone?  No.

Is a cone a special kind of scoop?  No.

So the correct answer is "Neither."  Most people got this; the most common
wrong answer was to say that SCOOP should have CONE as its parent, probably
because a scoop can be viewed as *part of* a cone.  But the parent/child
relationship isn't "a part of"; it's "a kind of."

(b) flavors method

(method (flavors)
  (map (LAMBDA (S) (ASK S 'FLAVOR)) scoops))

You *could* write the CONE class so that its instance variable SCOOPS would be
a list of flavors (i.e., names of flavors) instead of a list of scoop objects.
But that wouldn't be following the OOP paradigm.  (Not to mention that using
the name SCOOPS for a list of flavors would be really confusing!)  So if we
want to know the flavors in a cone, we have to ask each scoop for its flavor.

A few people said something like (USUAL 'FLAVOR) instead of (ASK S 'FLAVOR),
presumably because FLAVOR is a method of the SCOOP class, rather than of the
VANILLA or CHOCOLATE class.  But even if this could work, the whole idea of
inheritance is that you can send the child class (e.g., VANILLA) the same
messages you can send to the parent class (SCOOP).  You don't have to know
whether VANILLA handles the FLAVOR message itself or delegates the message to
its parent.  And in any case it wouldn't work; USUAL can only be used inside
a DEFINE-CLASS, because otherwise it doesn't know what object you're talking
about!


(c) adding a scoop

Given a particular ice cream cone, we want to add a particular scoop of
vanilla ice cream to it -- not the VANILLA class, and not the word VANILLA.
So the right answer is the last one listed:
	(ask my-cone 'add-scoop (instantiate vanilla))
The argument to INSTANTIATE is a class, not the name of a class.

Scoring: 2 points each.  No partial credit except that in part (B) leaving
out the quotation mark before FLAVOR got one point.