CS 61A		Fall 2000	Midterm #1 solutions

1.  What will Scheme print?  and B&P diagrams

(let ((a 3) (b 4))
  (lambda () (+ a b)))

PROCEDURE

	The body of the LET is (lambda () (+ a b)).  The value of that
	expression is a procedure -- after substitution, it's the same
	procedure as (lambda () 7).  But it's not the number 7, which was
	the most common wrong answer.  If we named this procedure P, then
	the expression (P) would mean to invoke P, and *that* would have the
	value 7.

(let ((a 3) (b 4))
  ((lambda () (* a b))))

12

	It's 12, not 7, because this one uses *, not +.  But the important
	thing is that those extra parentheses invoke the procedure, just like
	the (P) discussion above.  So the value isn't a procedure this time.
	Some people said 7 for the first example and procedure for this one;
	we haven't figured out what they were thinking.

(every - (filter number? '(the 1 after 909)))

(-1 -909)

	The FILTER part of the expression has the value (1 909), selecting the
	numbers from the given sentence.  (By the way, not everyone recognized
	this as the name of a Beatles song, from the album _Let It Be_, the
	last one they released, but the next-to-last one they recorded.)

	A few people thought this was a data abstraction violation, because
	FILTER returns a list, not a sentence, and EVERY definitely wants a
	sentence as argument.  I guess this could be confusing, but I defined
	in lecture during week 2 a FILTER that works on sentences, and that's
	the one we meant here.

	(every - '(1 909)) computes (- 1) and (- 909), putting the results in
	a sentence.  Some people thought this was an error because - requires
	two arguments, but it doesn't.  With one argument it means negation,
	rather than subtraction.  (Look it up in the Scheme reference manual
	at the back of your course reader!)

	A few people said -908, because they thought EVERY would call the
	function once, giving both numbers as arguments.  That would be
	(APPLY - '(1 909)), not EVERY.

Scoring for the above:  One point each, all or nothing.

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

    result =======>XX----------------------+
                   |                       |
                   |                       |
                   V                       V
                   XX-->X/         list===>XX-->X/
                   |    |                  |    |
                   |    |                  |    |
                   V    V                  |    V
                   a    b                  |    e
                                           |
                                           V
                                           XX-->X/
                                           |    |
                                           |    |
                                           V    V
                                           c    d

	In the diagram above I've indicated the result of the LIST
	subexpression.  The overall result shows, on the first line of
	the diagram, the one pair created by the CONS call.  Its car
	is (a b) and its cdr is the result from the LIST subexpression,
	which created two pairs.

	How does this print?  The pair created by the CONS has a list
	as its cdr, so it's a list, containing three elements.  The
	first element is (a b), the second is (c d), and the third is e:

		((a b) (c d) e)

	The most common mistake was to represent (a b) as a single pair,
	as if it were (a . b).  Another common mistake was to put an
	extra pair where the + sign is in the top line of the diagram,
	as if the CONS call were a LIST call.

	Please put a start arrow showing the pair at the head of your
	solution!  In some cases it was obvious which pair you meant,
	but sometimes it wasn't obvious.

(cddar '((a b c) (d e f) (g h i)))

	CDDAR means (cdr (cdr (car ...))) so we have

	   (car '((a b c) (d e f) (g h i))  ==>  (a b c)
	   (cdr '(a b c))                   ==>  (b c)
	   (cdr '(b c))                     ==>  (c)

	and the corresponding box-and-pointer diagram is just

	    --->X/
		|
		V
		c

	with a single pair as the spine of the one-element list.

	One common mistake was to think that a one-element list is the same
	thing as the element, so (cdr '(b c)) would be c, rather than (c).

	Another mistake was to put an extra pair in the diagram, as if
	the result were ((c)) -- a list containing (c) as its one element.

	The last common mistake was to compute the CADDR of the argument
	instead of the CDDAR, thinking that CDDAR means "first call cdr,
	then call cdr, then call car."  The caddr of this list is (g h i).

Scoring for these two parts:  1/2 point per printed form,
                              1/2 point per b&p diagram, rounded down.

Note:  There are no quotation marks in these lists!  The quotation marks
in the expressions tell Scheme not to evaluate the quoted value, but
they aren't part of the result.  For example, the value of 'E is E,
not 'E.  We took off a maximum of 1 point for any number of quotes in
the diagrams or printed forms.

General comment:  Arrows start inside a box, but end outside, so what I've
shown here as

   --->XX--->X/

(never mind the cars of the pairs) should be drawn

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

This is to remind you that the arrow comes *from* a particular half of a
pair (the car or the cdr), but points *to* the *entire* pair, not just to
half of it.  And there should be an arrowhead at the end of each arrow!


2.  Order of growth

(define (foo n)
  (if (< n 2)
      1
      (+ (baz (- n 1))
	 (baz (- n 2)) )))

(define (baz n)
  (+ n (- n 1)))

FOO is Theta(1).

	Since FOO calls BAZ twice, we have to know the running time of BAZ
	before we can figure out the running time of FOO.

	BAZ does not contain any recursive calls, either to baz itself or to
	foo.  Rather, it performs two fixed-time operations, an addition and a
	subtraction, and so its running time is Theta(1).

	Therefore, everything FOO does is fixed-time!  It calls <, +, -, and
	BAZ, all of which are Theta(1).  And so FOO itself is also Theta(1).

	The most frequent wrong answer was Theta(2^n).  People who thought
	that put too much weight on the *form* of procedure FOO.  They saw two
	procedure calls, and thought that the process was therefore comparable
	to the Fibonacci computation or the Pascal's Triangle computation.
	But in those cases, the two calls are *recursive* calls, not calls to
	a fixed-time helper.

(define (garply n)
  (if (= n 0)
      0
      (+ (factorial n) (garply (- n 1))) ))

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1))) ))

GARPLY is Theta(n^2).

	GARPLY calls itself recursively N times, so it's tempting to think
	that it's Theta(n), the most common wrong answer.  But each of those N
	invocations of GARPLY includes an invocation of FACTORIAL, which is
	itself Theta(n).  So N calls to a Theta(N) procedure makes a total of
	N*N fixed-time operations.

Scoring: one point each.


3.  Normal vs. applicative order

You can try this online:
STk> (load "~cs61a/lectures/1.1/order.scm")
STk> (def (mountain x) 'done)
STk> (def (dew) (dew))

STk> (normal (mountain (dew)))
(mountain (dew)) ----> 
(quote done)
done

	In normal order evaluation, we *don't* evaluate the subexpression
	(dew) first; we substitute the expression itself for X (the formal
	parameter) in the body of MOUNTAIN.  But that body is 'DONE, which
	doesn't contain X, so there's no substitution and we just evaluate
	'DONE, whose value is DONE.

	Note that the value is DONE, not 'DONE!  There are no quotes in
	the values Scheme produces for quoted words.

STk> (applic (mountain (dew)))
(mountain (dew))
   (dew) ----> 
   (dew) ----> 
   (dew) ----> 
   (dew) ----> 
   (dew*** Interrupt ***

	In applicative order, Scheme starts by evaluating the argument
	subexpression (DEW).  Since DEW has no arguments, there's nothing
	to substitute, and Scheme just evaluates the body, which is again
	(DEW), invoking the same procedure.  This is a recursion with no
	base case, which is an infinite loop.  So the answer we wanted
	is ERROR, but we accepted anything that shows understanding of
	what happens, e.g., "loop" or "infinite loop" was fine.

STk> (normal (mountain dew))
(mountain dew) ----> 
(quote done)
done

	Again, in normal order, the argument subexpression DEW isn't
	evaluated, but is substituted into the body as is.  But since
	X isn't used in the body, there's no substitution, and we
	just evaluate the body, which is 'DONE, whose value is DONE.

STk> (applic (mountain dew))
(mountain dew)
(mountain dew) ----> 
(quote done)
done

	Finally, in applicative order Scheme does evaluate the argument
	subexpression DEW first.  The value of that expression is a procedure.
	Since there are no parentheses around its name in the expression, we
	aren't *invoking* the procedure, so there is no infinite loop.

	Some people said "error -- unbound variable" for this one.  Why?  Both
	MOUNTAIN and DEW are defined; they're the names of procedures, which
	are perfectly good values.

Common wrong answers:

	ERROR, ERROR, DONE, DONE:  These people just used applicative
	order (which is what Scheme actually uses) all the time.

	DONE, ERROR, DONE, ERROR:  These people think that to name a
	procedure is to invoke it, ignoring the lack of parentheses in
	the second expression.

	DONE, PROCEDURE, DONE, ERROR:  I don't know what these people
	were thinking -- maybe that the expression (DEW) invokes DEW
	which returns DEW, as if it had been (define (dew) dew).

Score: 1/2 point per correct response, rounded down.


4.  Iterative vs. recursive process

(define (even? n)
  (cond ((= n 0) #t)
	((= n 1) #f)
	(else (if (even? (- n 2))
		  #t
		  #f))))

What happens when we say (even 5)?  The two base case checks fail, so
we get to the ELSE clause, which says
	(if (even? 3) #t #f)
This is a very unusual situation -- a recursive call as the *first*
argument to IF.  Ordinarily we have
	(if (non-recursive-function? x)
	    base-case-value
	    (recur (- x 1)))
or some such expression, in which the recursion is in the second or
third argument to IF.  In those cases, since IF is a special form,
it does most of its work before looking at the recursive call.  It
evaluates its first argument, checks whether the result is true or
false, and *finally* evaluates either the second or the third argument.
IF's job is finished by the time that recursive call is evaluated.

But in our problem, the recursive call is the first argument.  IF has
to do that recursive call, then wait to see if the result is true or
false, then finally use that true/false result to decide whether to
evaluate the second argument or the third one.

So this is a RECURSIVE process.  The little person doing (even? 5) has
to wait for the result from (even? 3) in order to choose whether to
evaluate #T or #F.

How to make it iterative?  As it turns out, we don't need that IF
expression altogether, since it merely duplicates the result that the
recursive call has already given us.  So we can say

(define (even? n)
  (cond ((= n 0) #t)
	((= n 1) #f)
	(else (even? (- n 2)))))

Now the result returned by the recursive call is used directly as the
return value from the calling invocation, so the process is iterative.

("Iterative" means "once the recursive call is finished, there is no more work
to do."  Some people who understand this definition still said that the
original version was iterative, because the extra work remaining after the
recursive call is unnecessary, the same argument I made in the paragraph
above.  But Scheme doesn't know the work is unnecessary, because it hasn't
looked at the second and third arguments to IF yet.)

Many people thought that a more complicated change to EVEN? was needed in
order to make it iterative, because their understanding of iteration focuses
on the *form* of a procedure.  They think that it's not iterative unless
there's a helper procedure, or that it's not iterative unless there's an extra
state variable.  Those things are often true, but they're not what "iterative"
means, and in this case there's no need for either of those things.  The idea
of iteration is about the meaning of a procedure, not the notation.

Scoring:  No points for thinking the original EVEN? generates an iterative
process.  One point for knowing it generates a recursive process but writing
a too-complicated attempt at an iterative version.  We accepted no change
other than the one shown above -- removing code, not adding code.  Two
points for the appropriate modification ("changing as little as possible,"
as the problem requires.)


5.  Twenty-one strategies.

This was the hardest problem because it asked you to write procedures.
But the people who solved it are the ones who kept track of the domain
and range of the procedures involved.

(a) RANDOM-STRATEGY takes a list-of-strategies as its argument, and
returns a strategy -- that is, a *procedure* that takes two arguments and
returns a true or false value.

(define (random-strategy list-of-strategies)
  (lambda (hand card)
    ((pick list-of-strategies) hand card)))

The least bad mistake, but still bad, was to say "Random-strategy is
supposed to return a strategy.  I have a list of them, so I'll pick one":

(define (random-strategy list-of strategies)	; wrong!
  (pick list-of-strategies))

This has the domain and range correct, but it picks a single strategy
from the list permanently.  The problem asks for a strategy that picks
one from the list each time it's invoked.

The other common errors were worse because they were confused about domain and
range.  Some people tried to make random-strategy a strategy itself:

(define (random-strategy list-of-strategies hand card)	; wrong!
  ...)

Other people made random-strategy return a procedure with the domain of a
strategy but with procedures rather than true/false values as its range:

(define (random-strategy list-of-strategies)	; wrong!
  (lambda (hand card)
    (pick list-of-strategies)))

Scoring: 2 points if correct.  We gave very few papers partial credit,
since almost all the mistakes were bad ones.  A couple of people got
one point for (lambda (hand) ...) instead of (lambda (hand card) ...).

(b) LOVELORN is a strategy!  So it takes a hand and a card as arguments,
and it returns true or false:

(define (lovelorn hand card)
  (empty? (filter (lambda (c) (equal? (last c) 'h))
		  hand)))

or

(define (lovelorn hand card)
  (not (member? 'h (every last hand))))

No credit for using the CS 3 every, which means something else.  No credit
for returning things other than #T and #F, such as the words 'HIT and 'STAY.
(After working on this project for a week you should know what a strategy
procedure does!)

No credit for solutions not using EVERY or FILTER -- those were part of
the purpose of the question.  We did give one point for trivial uses of
EVERY that didn't really advance the solution, such as
	(first (every last hand))
which really just does
	(last (first hand))
with a lot of extra effort.

Scoring:  2 if correct, 0 if wrong, except that we did give 1 point for
certain lesser mistakes:
	* BUTFIRST instead of LAST, etc.
	* Returns #T unless *all* cards in the hand are hearts.
	* Checks for aces instead of hearts.  (Why did this happen so often?)
	* (define (lovelorn hand) ...) with no card argument.


6.  Fill in the blanks.

Both DIAGONAL and CHOP do standard sequential recursion, of the form

	(define (recursion seq)
	  (if (null? seq)
	      '()
	      (COMBINE (SOMETHING (car seq))
		       (recursion (cdr seq)))))

except that DIAGONAL calls (diagonal (CHOP (cdr lstsents))) which is a
slight change from the standard pattern.  So the main problem here is to
figure out what combiner to use (in place of COMBINE above), and what
function of each element to compute (in place of SOMETHING above).

The other part of the problem is to keep the data abstraction straight.
This means understanding the domains and ranges of DIAGONAL and CHOP.
Both have the same domain: their argument is a list-of-sentences, which
is *not* a sentence!  So you want to use NULL?, CAR, CDR to examine it.
But they have different ranges: DIAGONAL returns a sentence, so you want
to use SENTENCE as the combiner; CHOP returns a list-of-sentences, so you
want to use CONS as the combiner.  Thus we have

(define (diagonal lstsents)
  (if (NULL? lstsents)
      '()
      (SENTENCE (FIRST (CAR lstsents))
		(diagonal (chop (CDR lstsents))))))

(define (chop lstsents)
  (if (NULL? lstsents)
      '()
      (CONS (BUTFIRST (CAR lstsents))
	    (chop (CDR lstsents)))))

The algorithm of CHOP is completely straightforward; as the comment given
with its definition says, it removes the first word from each sentence in
a list-of-sentences, so (CHOP '((A B C) (D E F) (G H I)) returns
((B C) (E F) (H I)).

The algorithm of DIAGONAL is a little trickier, because it does its
recursion on a CHOPped version of the cdr of its argument.  In the
example shown on the exam, it computes
	(sentence (first '(she loves you))
		  (diagonal '((me why) (want to hold your hand))))

Why FIRST and BUTFIRST in the solution above?  We'd use CAR and CDR to examine
the argument LSTSENTS, but here we are examining (CAR LSTSENTS), which is the
first sentence of the list-of-sentences, and therefore is a sentence.  CAR and
CDR would work for a sentence, but would violate the data abstraction.

In recursions on lists, the combiner is almost always CONS.  It's *never*
LIST!  Using LIST as the combiner in a recursion gives you nested two-element
lists, so you get (A (B (C (D ())))) instead of (A B C D).  On rare occasions
you want APPEND, because you want to flatten out the result of a recursion.
But in this case, using APPEND in CHOP would give you one long sentence, not a
list-of-sentences.

Scoring:  1/2 point off per data abstraction violation (EMPTY? for NULL?,
CAR for FIRST or vice versa, CDR for BUTFIRST or vice versa, SENTENCE for
CONS or vice versa).  One point off for each other error (LIST for CONS,
etc.) that would affect the result of calling the procedures.