CS 61A		Fall 1994	Midterm #1 solutions

1.  What will Scheme print?

> (lambda (x y) x)
PROCEDURE

	[Lambda returns a procedure.  Simple as that.]


> (* (+ 2 3) (+ 2 6))
40


> (first '(help!))
HELP!

	[The first of a *sentence* containing one word is that word.
	If you had parentheses in your answer, that's wrong -- it
	would then be a sentence, not a word.  The obvious wrong
	answer is H, which would be correct for (first 'help!).
	A more unusual wrong answer was "(" -- thinking, I guess,
	that the parentheses are just characters in a word, the same
	as the exclamation point.  But the parentheses that delimit
	a sentence are not *part of* that sentence.]


> ((word 'but 'first) 'plop)
ERROR

	[This is the one most people got wrong.  Of course it's
	equivalent to ('butfirst 'plop), but that's *not* the same
	as (butfirst 'plop)!  Think about the following example:
		> (define x 7)
		> (+ x 5)
		> (+ 'x 5)
	The second expression has the value 12.  What about the third
	expression?  It's an error; you can't add the word "x" to a
	number.  The word "x" is not the same as the thing whose name
	is "x".  Similarly, the word "butfirst" is not the same as the
	thing whose name is "butfirst".]


> (let ((+ -)
        (- +))
    (- 8 2))
10

	[Names of primitives are just ordinary variables that happen
	to have a predefined value, but that can be overridden by a
	local binding.  Notice that that isn't true about names of
	special forms; you can't say (LET ((DEFINE +)) ...) etc.
	Since all the bindings in a LET are done at once, not in
	sequence, the local value for the name "-" is the *original*
	meaning of +, not the local meaning.]


> ((lambda (z) (- z z)) (random 10))
0

	[Some people said "0 if applicative order, some random value
	if normal order."  That's true, but the point of the question
	was to see if you know what Scheme does!]


Scoring: 1/2 point each, rounded up.


2.  Which are linear time?

(a) Find the largest of a sentence of numbers.

YES.  We don't have to compare every number with every other number,
which would be O(N^2).  We merely have to compare every number with
the largest found so far:

(define (largest nums)
  (define (helper max-so-far rest)
    (cond ((empty? rest) max-so-far)
	  ((< max-so-far (first rest)) (helper (first rest) (bf rest)))
	  (else (helper max-so-far (bf rest)))))
  (helper (first nums) (bf nums)))


(b) Find out whether a sentence contains two equal words.

NO.  Suppose the sentence doesn't have two equal words.  In order to be
sure of that, we have to compare every word against every other word,
so this is O(N^2).  [We could improve the efficiency of this operation
by sorting the sentence first, using an O(N log N) sort algorithm; then
if there are two equal words they'll be next to each other in the sorted
sentence, so we can merely compare adjacent words.  But it's still more
than linear time.]

(define (two-equal? wds)
  (cond ((empty? wds) #f)
	((member? (first wds) (bf wds)) #t)
	(else (two-equal? (bf wds)))))

This procedure may look like a simple linear process, but MEMBER? is
itself an operation that involves looking at every word in the sentence:

(define (member? this those)
  (cond ((empty? those) #f)
	((equal? this (first those)) #t)
	(else (member? this (bf those)))))


(c) Find out whether or not all the words in a sentence are equal.

YES.  Here we don't have to compare each word with each other word;
we merely compare each word with one fixed word that we take as the
reference:

(define (all-equal? sent)
  (define (helper value candidates)
    (cond ((empty? candidates) #t)
	  ((equal? (first candidates) value)
	   (helper value (bf candidates)))
	  (else #f)))
  (if (empty? sent)
      #t
      (helper (first sent) (bf sent))))

[Why is the correct result #T if the sentence is empty?  One way
to think about it is that "all the words in this sentence are equal"
means the same as "there are no two unequal words in this sentence."
For a more formal way to think about it, take Math 55.]

Scoring: One point, all or nothing.


3.  Censor numbers.

(define (cia sent)
  (cond ((empty? sent) '())
	((number? (first sent))
	 (se 'omitted (cia (bf sent))))
	(else (se (first sent) (cia (bf sent))))))

This can also be done with a higher-order function:

(define (cia sent)
  (mapcar (lambda (wd) (if (number? wd) 'omitted wd)) sent))

Common errors:

* Instead of using the primitive NUMBER?, checking only the first
character of a word to see if it's a digit.  (If you really want to
write NUMBER? yourself, you can, but you have to check every
character, not just the first, and you have to worry about things
like a minus sign as the first character, and a decimal point--but
only one--in the middle somewhere.)

* Another wrong way to check for a number was (not (word? (first sent))).
Numbers ARE words!

* In the else clause, leaving out the (se (first sent) ...) part.
My guess is that you're thinking about it as if you were doing it
on paper, where you'd cross out numbers but leave other words
alone.  There's no "leave it alone" here because we're not
modifying the input sentence "in place"; rather, we're creating
a new sentence that includes some of the words of the input sentence.

* Somewhat along the same lines, saying just 'OMITTED instead of
(se 'omitted (cia (bf sent))) for the case of a number.  Probably
you thought that the program would print OMITTED and then continue
on to the else clause, or something like that.  But a function
returns only one value; it doesn't return one thing and then keep
going to return more things.  That's why you need a constructor like
SENTENCE to combine the pieces.

Scoring:  The standard BH 5-point scale:
	5    correct except maybe some right parentheses missing.
	3-4  has the idea
	1-2  has an idea
	0    other

In this case, "has the idea" means that it's recursive or the equivalent
with mapcar, and combines either OMITTED or the first word with a recursive
result for the other words.


4.  Test-both.

(define (test-both pred1 pred2)
  (lambda (x) (and (pred1 x) (pred2 x))))

> (define foo (test-both > =))
FOO
> (foo 8 5)
ERROR		[both because FOO takes one argument and because
 		 < and = take two arguments!]
> ((test-both empty? word?) '())
#F		[the empty sentence isn't a word]
> ((test-both number? 5) 2)
ERROR		[5 isn't a predicate; you can't invoke 5 with 2 as argument]


All of the common mistakes had to do with not understanding the domains
and ranges of the functions involved.

TEST-BOTH takes two arguments, each of which is a predicate function,
and returns a predicate function.

PRED1 and PRED2 take one argument and return #T or #F.

The function returned by TEST-BOTH also takes one argument and
returns #T or #F.

If you had no lambda at all, then you are saying that TEST-BOTH
returns #T or #F, instead of returning a function.

If you had (lambda (x y) ...) then you're saying the function
returned by TEST-BOTH takes two arguments.

If you said (and (lambda (x) ...) (lambda (x) ...)) then you're
confused about the difference between a function and its range;
you think that AND takes functions as arguments instead of
taking #t/#f as arguments.

Scoring: One point for part (b), with one error allowed.  (We
didn't care what you said the DEFINE returns, as long as you
didn't say it's an error.)  For part (a), 4 if correct, 2-3 if
has the idea, 1 if has an idea, 0 other.


5.  CAN-ADD?

There are many ways to do this.  Probably the most elegant is

(define (can-add? sum addends)
  (cond ((empty? addends) #f)
	((member? (- sum (first addends)) (bf addends)) #t)
	(else (can-add? sum (bf addends)))))

If you didn't think to use subtraction to help, you can get the
same general structure by writing your own procedure to use in
place of MEMBER? above:

(define (can-add? sum addends)
  (define (can-add-using? addend others)
    (cond ((empty? others) #f)
	  ((= (+ addend (first others)) sum) #t)
	  (else (can-add-using? addend (bf others)))))
  (cond ((empty? addends) #f)
	((can-add-using? (first addends) (bf addends)) #t)
	(else (can-add? sum (bf addends)))))

Either way, the crucial point is that the program structure is
two-dimensional because you have to check every possible PAIR of
numbers -- every number with every other number.  This Scheme
program in which an iterative-process procedure uses an
iterative-process helper is comparable to the nested loop
construction you may have seen in other languages:
 	for I := 1 to N do begin
 	  for J := I+1 to N do begin
 	    ... if (sum = addends[I] + addends[J]) then ...
 	  end;
 	end;
except that we don't have to use index variables like I and J,
and we don't have to know how big the sentence is.

Another okay approach is to generate all the possible sums of pairs
of addends and see if SUM is among them:

(define (can-add? sum addends)
  (member? sum (all-sums addends)))

(define (all-sums nums)
  (if (empty? nums)
      '()
      (se (add-to-each (first nums) (bf nums))
	  (all-sums (bf nums)))))

(define (add-to-each this those)
  (if (empty? nums)
      '()
      (se (+ this (first those))
	  (add-to-each this (bf those)))))


It's also possible to make this work with a single iterative
procedure, but it's much more intricate, harder to read, and
harder to debug:

(define (can-add? sum addends)
  (define (helper first-addend-candidate second-addend-candidates untried)
    (cond ((and (empty? untried) (empty? second-addend-candidates)) #f)
	  ((empty? second-addend-candidates)
	   (helper (first untried) (bf untried) (bf untried)))
	  ((= sum (+ first-addend-candidate
		     (first second-addend-candidates)))
	   #t)
	  (else (helper first-addend-candidate
			(bf second-addend-candidates)
			untried))))
  (if (empty? addends)
      #f
      (helper (first addends) (bf addends) (bf addends))))

Common errors:

* Using (empty? (bf addends)) as the base case test.  Several of you
complained about losing a point for this, because we said "don't put
in error checks," but it's not an error for a sentence of numbers to
be empty.  An error would be if the sentence contained non-numeric
words.

* Algorithms that only work for nonnegative integers, e.g., generate
all the integers from 0 to SUM and look for them in the ADDENDS sentence.

* Adding up all the numbers in ADDENDS instead of just two at a time.

* Adding a number to a sentence, e.g., (+ (first addends) (bf addends)).
This is pretty bad; it means you aren't thinking about the domains and
ranges of the functions you're using.

* Only checking adjacent addends: (+ (first addends) (first (bf addends))).

* Building the given examples into the program, e.g., one that works
only if SUM is 7, or only if there are exactly five ADDENDS.  This is
really terrible -- in general, you get zero points if you build a
specific example into a program on a test.

* A particularly bad version of building specific examples into the
program is to try to build them into the formal parameters of a
procedure, e.g., (define (can-add? sum '(a b c d e)) ...)  No!!!

Although this isn't in itself an error, several former C or Pascal
programmers wrote programs with index variables, and/or using COUNT,
and those incredibly complicated programs often turned out not to
work because some boundary condition wasn't quite right -- you didn't
check the last possible addend, or something like that.  Try to
write Schemely programs, not line-by-line translations from C.

Don't put in special-case checks like (> (first addends) sum).
In this case it isn't even correct, because another addend could
be negative.  But even if it were correct to rule out large
addends, the cost of checking each time probably outweighs the
cost of just trying all the possible sums, and special cases
increase the chance of program errors.

Scoring: Standard BH scale.  Having the idea means at least an O(N^2)
algorithm.