CS 3		Spring, 1994		Midterm 2 solutions

1.  What's the value?

> (map (lambda (x) (+ 3 (cadr x))) '((1 2 3) (4 5 6) (7 8 9)))
(5 8 11)

	This is equivalent to
	(list (+ 3 (cadr '(1 2 3)))
	      (+ 3 (cadr '(4 5 6)))
	      (+ 3 (cadr '(7 8 9))))

> (append 'for '(no one))
ERROR

	The arguments to append must be lists, not words.  (Some versions of
	Scheme will let you get away with a word as the last argument to
	append, but not for anything before the last one.  Never mind why,
	until you take 61A.  For our purposes, they all have to be lists.)

> ((lambda (a) (cons (cadr a) a)) '(w x y z))
(X W X Y Z)

	This is equivalent to
	(cons (cadr '(w x y z)) '(w x y z))
	Most people got it, but the common errors were to think it returned
	a procedure (not noticing that the lambda expression is the first
	subexpression of a larger expression) or to throw in some extra
	parentheses, e.g., ((X) W X Y Z).  A few people had A as part of
	their answer; A is a formal parameter, not data!

> (first (bf (cadr (cadr '((john lennon) (paul mccartney)
			   (george harrison) (ringo starr))))))
C

	(cadr '((j l) (p m) (g h) (r s)))  ==> (paul mccartney)
	(cadr '(paul mccartney))           ==> mccartney
	(bf 'mccartney)			   ==> ccartney
	(first 'ccartney)		   ==> c


Scoring: 1/2 point each, rounding up.


2.  Geography

(define (geography? sent)
  (cond ((<= (count sent) 1) #t)
	((equal? (last (first sent))
		 (first (first (bf sent))))
	 (geography? (bf sent)))
	(else #f)))

Scoring: 4 correct, 2-3 has the idea, 1 has an idea, 0 other.

Typical 3-point answers:  #t/#f backwards, just empty sent as base case,
(caadr sent) instead of (first (first (bf sent))) [because you can't take
car of a word!], just (first (bf sent)) instead of two firsts.

Typical 2-point answers:  (first (last sent)) instead of (first (first (bf
sent))), (bf (bf sent)) in the recursive call [which would only look at
every other word pair], or writing a procedure that returns true if ANY pair
of words is okay, rather than if ALL of them are okay.

Typical 1-point or 0-point answers aren't predicates (don't return #t or #f)
or were just bizarre.

Strictly speaking, the program should test for both empty sentences and
one-word sentences as base cases.  If you only have empty sentences as the
base case, your program will blow up when you try to take (first (bf
sent)).  If you only have one-word sentences, then your program will work
fine unless you are actually given an empty sentence as argument, so we
didn't take off for that case.


3.  Maprest.

The solution we wanted is

(define (maprest fn lst)
  (if (null? lst)
      '()
      (cons (fn lst)
	    (maprest fn (cdr lst)))))

There really is no other good way to do this.  Compare the definition of map
(page 328 of the text):

(define (map fn lst)
  (if (null? lst)
      '()
      (cons (fn (CAR lst))
	    (map fn (cdr lst)))))

The only difference is that for maprest you leave out the CAR that's in
capital letters in map above.  Think about it -- map applies fn to the car
of its argument list; maprest applies fn to the whole list!


Many people tried to do it by creating a list of lists and then either using
or rewriting map:

(define (maprest fn lst)	;; uses HOF
  (map fn (tails lst)))

(define (tails lst)
  (if (null? lst)
      '()
      (cons lst (tails (cdr lst)))))

This solution is correct apart from violating the rule about no HOFs, but it
does a lot more work than necessary.


Many other people had the same idea, but tried to do it all in one procedure:

(define (maprest fn lst)	;; wrong!!
  (if (null? lst)
      '()
      (cons (fn (car (tails lst)))
	    (maprest fn (cdr (tails lst))))))

or similar constructions.  What these wrong solutions have in common is that
maprest expects a list of elements, but you call it recursively with a list
of tails.  Then a list of tails of lists of tails, etc.  If you don't see
why this is wrong, trace it!

Typical 3-point answer: bf instead of cdr.  (We said it should work for
lists, not sentences or words.)

Typical 2-point answer: Wrong combiner -- list or append or se instead of
cons; or correct answer using HOF.

Typical 1-point answer: Taking the car of lst, so you essentially reinvented
map.


4.  Smallest-sum

People seemed to have a lot of trouble with this problem.  One way to
approach a problem like this is to try writing it with HOFs, even though the
problem says not to, and then translate.  So, the hint says "choose the
subtree with the smallest smallest-sum" and that leads me to this procedure:

(define (smallest-sum tree)	;; correct but uses HOFs
  (if (leaf? tree)
      (datum tree)
      (+ (datum tree)
	 (reduce min (map smallest-sum (children tree))))))

To eliminate the use of higher-order functions we must write a version with
mutual recursion, like the example on page 302.  Combining reduce with map
is sort of like the Combining Patterns examples on pages 220-221.

(define (smallest-sum tree)
  (if (leaf? tree)
      (datum tree)
      (+ (datum tree)
	 (smallest-sum-forest (children tree)))))

(define (smallest-sum-forest forest)
  (if (null? (cdr forest))
      (smallest-sum (car forest))
      (min (smallest-sum (car forest))
	   (smallest-sum-forest (cdr forest)))))

Many, many people just copied count-leaves from page 302.  C'mon, folks, if
that program counts the number of leaves in a tree, it's not suddenly going
to find the smallest path from the root to a leaf just because you change its
name!  For example, count-leaves pays no attention to the actual data in the
tree.  (That is, it doesn't invoke datum anywhere.)  That obviously won't
work here.

How come count-leaves has a + in the forest helper, but smallest-sum does
its + in the top-level procedure?  Well, draw a picture of a tree and circle
the leaves.  You'll see that to find the leaves you must move horizontally
across the bottom of the tree.  Now look at the picture in the exam problem,
and you'll see that to get the answer you must move vertically, adding the
data along a path from the root to a particular leaf node.  (Don't just
write down "horizontal=forest, vertical=tree" in your notes!  Work through
both programs by hand and convince yourself of why they make sense.)

If you can't quite see how to get from the HOF version to the one with
smallest-sum-forest, you could handle the map and the reduce separately,
using the patterns in Chapter 14.  (A few people just wrote map themselves,
and we let them get away with it, but if you know how to write map you
should know how to specialize it to work with a particular function!)

(define (smallest-sum tree)
  (if (leaf? tree)
      (datum tree)
      (+ (datum tree)
	 (minimize (all-smallest-sums (children tree))))))

(define (all-smallest-sums forest)
  (if (null? forest)
      '()
      (cons (smallest-sum (car forest))
	    (all-smallest-sums (cdr forest)))))

(define (minimize nums)
  (if (null? (cdr nums))
      (car nums)
      (min (car nums) (minimize (cdr nums)))))

All-smallest-sums is exactly like the EVERY examples on page 216, except
that the combiner is CONS, as in the definition of MAP on page 328.  (Don't
get the idea that you're supposed to flip wildly through the textbook during
the test!  You're supposed to understand *why* cons is the combiner for map,
and be able to figure it out when you have to.)

Minimize is just like sent-max on page 20, but for lists instead of
sentences.  The only tricky part is that the base case isn't an empty list,
because there's no identity element for min.  See the top of page 220, and
all of page 330.

Scoring: 5 correct, 3-4 has the idea, 1-2 has an idea, 0 other.
Having the idea includes knowing the difference between a tree and a
forest, so you don't say things like (smallest-sum (cdr forest)), and
actually taking the min of something.  An otherwise correct answer using
higher-order procedures got 3 points.  One way to get zero points was to
build the specific example into the program.  The worst of these was a
program that added 10 (the value at the root of our example tree) to
something, but several other people had programs that only worked if every
branch node has exactly three children!