CS 61A		Fall 1997	Midterm #1 solutions

0.  Name, etc.

Many groups lost this point because they had no identifying information
at all on the inside pages.  We don't insist on everyone's full name for
the group papers, but at least the logins, or the group number, or something!
Otherwise when pages get separated it's a big disaster.

Many people did not read and/or sign the box on the front that said
READ AND SIGN THIS in big bold letters.  We didn't take off the question 0
point for that, this time, but we will from now on.

1.  What will Scheme print?

> (first (bf (first (bf '(back in the ussr)))))
N

	(bf '(back in the ussr)) --> (in the ussr)
	(first '(in the ussr))   --> in
	(bf 'in)                 --> n
	(first 'n)               --> n

	One common wrong answer, "error," probably came from confusing
	butfirst with last, or from thinking that a one-letter word
	doesn't have a first letter.

	Another common wrong answer was (N) -- a sentence containing
	the word N.  Words and sentences are two different kinds of
	data; this problem will be seen again in base case errors
	later in the exam.

> '(+ 6 7)
(+ 6 7)

	The value of a quoted sentence is that sentence, even if the
	sentence looks like a Scheme expression.

	The value does NOT, however, include the quotation mark.

> ((lambda (x y) y) 8 3)
3

	Most everyone got this.

> (+ '(3 4 5))
ERROR

	The domain of the + function is numbers, not sentences,
	not even sentences containing numbers.

> (let ((a +)
	(* 3))
    (a * *))
6

	After substitution from the LET, the body means (+ 3 3).
	The most common mistake was "error," probably because people
	thought that the symbol * has some special status and can't
	be a local variable name.  There's nothing special about the
	names of primitives, not even the ones with punctuation characters.

> (if 6 7 8)
7

	Anything other than #F is true, therefore 6 is true, therefore
	the IF will evaluate its second argument expression.

Scoring: 1/2 point each, rounded down.


2.  What kind of process?

Recursive.  The recursive call provides an argument to a larger expression:

	(+ n (triangle (- n 1)))

When the lower-level TRIANGLE finishes its work, the higher-level one
still needs to add its result to N.  It's an iterative process only if
the higher-level invocation has nothing left to do after the recursive
invocation.  Most people got this right.

Scoring: 1 point!


3. Diagonal.

The most straightforward solution, I think, uses a helper procedure
(in addition to ITEM):

(define (diagonal sent)
  (diag-help sent 1))

(define (diag-help wds num)
  (if (empty? wds)
      '()
      (sentence (item num (first wds))
		(help (butfirst wds) (+ num 1)))))

The helper can be an internal definition if you like.

A more concise solution without a helper can be written if you think
to go from right to left.  Why would you think of that?  Because
(diagonal (butlast sent)) is part of the solution for the original
problem, whereas (diagonal (butfirst sent)) is not.  For example:

(diagonal '(in my life))   -->  (I Y F)
(diagonal '(in my))        -->  (I Y)
(diagonal '(my life))      -->  (M I)

(I Y) is part of (I Y F), but (M I) is not.  This idea leads to
the following solution:

(define (diagonal sent)
  (if (empty? sent)
      '()
      (sentence (diagonal (butlast sent))
		(item (count sent) (last sent)))))

Left-to-right solutions without helpers are really messy.

Scoring (for all the programming problems, numbers 3 to 5):

4     correct
3     correct but really hideous
2-3   has the idea
1     has an idea
0     other

The most common error, earning 3 points, was to get the base case
wrong, as follows:

(define (diag-help wds num)
  (if (empty? (BUTFIRST wds))
      (ITEM NUM (FIRST WDS))
      (sentence (item num (first wds))
		(help (butfirst wds) (+ num 1)))))

This is wrong because with a one-word argument it returns a word,
not a sentence.  If the range of a procedure is sentences, then
it must always return a sentence, even in the base case.  The returned
word from the base case will indeed be combined with other words to
form a sentence if the original argument has more than one word, but
the procedure must work correctly even if the original argument is
exactly one word.

	(diagonal '(hello))       --> (H)       not H!

A correct solution with that base condition would have to be

(define (diag-help wds num)
  (if (empty? (butfirst wds))
      (SENTENCE (item num (first wds)))
      (sentence (item num (first wds))
		(help (butfirst wds) (+ num 1)))))

There are two morals to this:

1.  Your procedure's range must be consistent.  If it returns something
of a particular type in general (word, sentence, number, whatever) then
it must return something of that type in the base case, too.

2.  Your life will be much easier if you use an empty base case
(or zero, for numeric problems) instead of a length-one base case.

By the way, some people included simulated test cases for all the
programming questions.  We want you to *actually* test your *projects*
by running them on a computer!  But it's not necessary to pretend-test
the programs you write on exams.  (It's okay if you did that just to
convince *yourself* that your answer was correct, though.)


4.  Table

This question is almost exactly like one of the examples in the book,
so we expected everyone to get it, and most did, using the same form
as the book's version:

(define (table fn from to)
  (if (> from to)
      '()
      (sentence (fn from)
		(table fn (+ from 1) to))))

It was also possible to use one of the homework problems to solve this:

(define (table fn from to)
  (accumulate sentence '() fn from (lambda (x) (+ x 1)) to))

Again, the most common wrong answer messed up the base case:

(define (table fn from to)
  (if (= from to)
      (FN FROM)
      (sentence (fn from)
		(table fn (+ from 1) to))))

The range of this procedure is sentences, so if you want to use
(= from to) as the end test, then you must return (SENTENCE (fn from))
in that case.  The same two morals apply as in question 3.

A less common wrong answer had a LAMBDA in the definition of TABLE.
Although a lambda expression was used as an *argument* to TABLE, in
one of the examples, TABLE itself does not return a procedure.
Its range is sentences.


5.  Echo.

There are basically two ways to do this.  Probably the more obvious
one is to use a helper procedure:

(define (echo n)
  (lambda (wd) (echo-help wd n))

(define (echo-help wd n)
  (if (= n 0)
      '()
      (sentence wd (echo-help wd (- n 1)))))

If you don't want to use a helper (which can, of course, be defined
inside ECHO), then you need a tricky form of recursion:

(define (echo n)
  (lambda (wd)
    (if (= n 0)
	'()
	(sentence wd ((echo (- n 1)) wd)))))

Note the two open parentheses before the call to echo!!  The expression

	(echo (- n 1))

returns a procedure, and the outer expression

	( .... wd)

(putting the first expression in place of the ....) invokes that procedure
with WD as its argument.

This was the hardest problem for most people.  There were three common
serious mistakes:

Recursive call to ECHO but the result not invoked (score 2 or less).
No lambda (score 1 or less).
No recursion at all (score 1 or less).

In addition, there was the same base-case-wrong-type problem that came
up in the other questions:

(define (echo n)		;; wrong!
  (if (= n 0)
      '()
      (lambda (wd) ...)))

Another moral:  Before you write any procedure, ask yourself:
	"What is the domain of this procedure supposed to be?"
	"What is the range of this procedure supposed to be?"
and then make sure your procedure really does have that domain and range.

Another error, thankfully uncommon but very serious, was to build
the number 3 and/or 5 (the ones used in the examples) into the
procedure.  If you do that, you're failing to understand the entire
idea of a procedure!


6.  Towers of Hanoi program.

(a) The value of (foo 3) is

	(1 2 1 3 1 2 1)

It's the order in which to move the disks when solving the Towers of Hanoi
puzzle with three disks.  (Never mind if you don't know the puzzle.)


(b) How many times is FOO invoked?

15.  The key point is that there are eight invocations, with N=0, that
don't contribute anything to the returned value.

Some people thought that we didn't want to count the (foo 3) call itself,
so we accepted 14 also.


(c) To keep the same result but leave out half the invocations, we
use 1 as the base case instead of 0:

(define (foo n)
  (if (= n 1)
      '(1)
      ...))

As I've been saying repeatedly, the procedure must return a value in its
specified range in the base case, too, so the result must be the sentence
(1) and not just the number 1.

P.S.  We asked this question because we want you to understand how base
cases work.  But if you are asked to write a program for this problem,
don't really use 1 as the base case!  The constant-factor efficiency
issue is outweighed by the cleaner code, and also, zero is a perfectly
reasonable argument, with a well-defined return value (namely an
empty sentence), and using 1 as the base case needlessly restricts
the domain of the procedure.

Scoring: one point each.

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

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!