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.