CS 61A		Spring 1995	Midterm #1 solutions

1.  What will Scheme print?

> (first (butfirst '(yesterday)))
ERROR

	['(yesterday) is a sentence of length 1.  Its butfirst is therefore
	an empty sentence.  First of an empty sentence is an error.]


> ((lambda (x) x) (lambda (x) x))
PROCEDURE

	[The expression ((lambda (x) x) --ANYTHING--) is the same as just
	typing the anything; the procedure just returns its argument.  So
	in this case, the entire expression is the same as if we'd just
	typed (lambda (x) x) -- that is, the second one -- and the value
	of that expression is a procedure.]


> ((lambda (w) (sentence (word 'h w) (word 'th w))) 'ere)
(HERE THERE)

	[Substitute 'ere for w in the body, and you get the expression
	(sentence (word 'h 'ere) (word 'th 'ere)).]


> (+ (* 3 5 0 7) (- 8 2))
6

	[I think everybody got this one!]


> (and (> 2 3) (/ 5 0))
#F

	[AND is a special form.  It evaluates its arguments from left
	to right, and as soon as any argument is false, it stops.  So
	the second argument expression is never evaluated.]


> (let ((me 'you)
	(you 'me))
    (sentence 'you 'love me))
(YOU LOVE YOU)

	[The quoted words 'you and 'love evaluate to YOU and LOVE
	regardless of any variable bindings.  The unquoted word ME
	is a variable reference, for which its value, YOU, is
	substituted.]


Scoring: 1/2 point each, rounded down, except that you only lost 1/2 point
once for leaving out the parentheses in the two sentences, and you only lost
1/2 point once for quoting the two sentences.  [Please be sure you understand
that it's wrong to quote them!  Scheme does NOT print '(HERE THERE) for the
third example, etc.]


2.  List the calls to ALL-VOWELS? in this:

(define (all-vowels? wd)
  (cond ((empty? wd) #t)
	((vowel? (first wd)) (all-vowels? (bf wd)))
	(else #f)))

(define (keep-all-vowels sent)
  (cond ((empty? sent) '())
	((all-vowels? (first sent))
	 (se (first sent) (keep-all-vowels (bf sent))))
	(else (keep-all-vowels (bf sent)))))

> (keep-all-vowels '(eva ai xxx a))

(ALL-VOWELS? 'EVA)
(ALL-VOWELS? 'VA)

(ALL-VOWELS? 'AI)
(ALL-VOWELS? 'I)
(ALL-VOWELS? "")

(ALL-VOWELS? 'XXX)

(ALL-VOWELS? 'A)
(ALL-VOWELS? "")

for a total of eight calls.  The key point is that once a consonant is
seen, there are no more recursive calls for that word.

Scoring:

3  correct
2  missing the base-case calls, or one extra call
1  two or more wrong, or keep going after consonants
0  no recursive calls, or a call per individual letter

We didn't take off if you said '() instead of "" because that distinction
wasn't the point of this problem, but you should know that the empty word
and the empty sentence are two different things!


3.  make-false-ok

Several solutions are possible.  The most straightforward is

(define (make-false-ok oper)
  (lambda (x y)
    (if (or (equal? x #f) (equal? y #f))
	#f
	(oper x y))))

Brandy's more elegant solution, taking advantage of the fact
that AND is a special form:

(define (make-false-ok oper)
  (lambda (x y)
    (and x y (oper x y))))

There are intermediately elegant ones like (if (and x y) (oper x y) #f).

We didn't take off for tests involving NUMBER? or BOOLEAN? even though
a strict reading of the problem tells you that the only special case value
for the arguments is #F.

Scoring:

5  correct.

4  uses = instead of EQUAL? to test non-numbers.
   uses + as a formal parameter.  (This can work, but is really ugly.)
   incorrect test condition, e.g., (or x y).

3  doesn't do (oper x y) but does get (lambda (oper) (lambda (x y) ...))
     and isn't bizarre.  [There were only a few special cases about this.]

2  returns a function, but not an appropriate one, e.g., not one with two args.

1  creates a function with lambda, but then invokes it instead of returning it.

0  no lambda at all.
   has the specific example built in, e.g., (> x 30) or something.


4.  Modify count-coins into a predicate

(define (change-possible? amount coin-sent)
  (cond ((= amount 0)  #T )
                      ----
	((or (< amount 0) (empty? coin-sent))  #F )
                                              ----
	(else ( OR  (change-possible? (- amount (first coin-sent))
               ----
				      coin-sent)
		    (change-possible? amount (bf coin-sent))))))


Scoring:

3  correct
2  a correct procedure not following the framework, e.g., (if (not ...) ...)
      instead of (or ...)
1  gets the wrong answer, but at least a Boolean answer, e.g., base cases
      backwards
0  doesn't even always return a Boolean


5.  Two-twice?

The most straightforward solution:

(define (two-twice? wd)
  (cond ((< (count wd) 3) #f)
	((substring? (word (first wd) (second wd)) (bf wd)) #t)
	(else (two-twice? (bf wd)))))

(define (substring? two wd)
  (cond ((< (count wd) 2) #f)
	((equal? two (word (first wd) (second wd))) #t)
	(else (substring? two (bf wd)))))

Another equally good solution:

(define (two-twice? wd)
  (define (helper twos)
    (cond ((empty? twos) #f)
	  ((member? (first twos) (bf twos)) #t)
	  (else (helper (bf twos)))))
  (helper (make-twos wd)))

(define (make-twos wd)
  (if (< (count wd) 2)
      '()
      (sentence (word (first wd) (second wd))
		(make-twos (bf wd)))))

Yet another, not-so-obvious one:

(define (two-twice? wd)
  (cond ((< (count wd) 3) #f)
	((and (equal? (first wd) (last (butlast wd)))
	      (equal? (second wd) (last wd)))
	 #t)
	(else (or (two-twice? (butfirst wd))
		  (two-twice? (butlast wd))))))

Some people misunderstood what the problem was asking, because of not
thinking hard enough about the examples shown.  For example, if your
program includes (member? (first wd) (bf wd)) then you are answering
the question "are there two letters, each of which appears twice in
the word?" instead of the question "is there a pair of consecutive
letters that appears twice in the word?"

On the other hand, if your program includes
	(member? (word (first wd) (second wd)) (bf wd))
then what you don't understand is how the MEMBER? procedure works!
Only a single letter can be a member of a word.

Scoring:

5  correct.

4  error in base case.
   (bf (bf wd)) in recursion.

3  uses (MEMBER? (FIRST WD) (SECOND WD) (BF WD)) or equivalent.

2  compares single letters.
   compares only adjacent letters or pairs.

1  not a predicate, or really off the wall.

0  even more off the wall than that.
   has specific example words (e.g., banana) built in.