CS 61A Fall 2008 Midterm 1 solutions 1. What will Scheme print? (accumulate word (map (lambda (x) (remainder x 2)) '(1 2 3 4 5 6 7))) Answer: 1010101 The result of the MAP call is (1 0 1 0 1 0 1), and the ACCUMULATE call makes a word out of the elements of that list. (By the way, this word is itself a number: one million, ten thousand, one hundred one.) Because there was confusion (our fault) about whether we intended the version of ACCUMULATE that requires a base case argument, we also accepted ERROR for this question. (or #f 3 #t) Answer: 3 OR is a special form; it evaluates its arguments from left to right, stopping as soon as it finds a true value, and returns that value. Since anything other than #F is true, the second argument, 3, is true. So that's what OR returns. ((lambda (x) (x x x)) 7) Answer: ERROR (attempt to apply non-procedure 7) If it had said (lambda (x) (LIST x x x)) then the answer would have been (7 7 7). But (X X X) is an attempt to invoke X (which is 7 in this procedure call) as a procedure, like typing (7 7 7). (let ((+ *) (a (+ 2 3))) (+ a 10)) Answer: 50 This is a problem about understanding how a LET expression is evaluated. The first step is that all the actual argument expressions [in this case, * and (+ 2 3)] are evaluated! This happens before any substitution of values for variable names. So the + sign in (+ 2 3) means the globally defined +, the addition function. Therefore A has the value 5. Only after all these expressions are evaluated do we assign values to the LET variables (in this case, + and A). Substituting into the body of the LET, we get (* 5 10). [Technically, we get (#[CLOSURE ...] 5 10) because it's the multiplication procedure, not the asterisk, that becomes the value of the + symbol.] Expected wrong answers are 60, if you thought the replacement of + with * affects the calculation of A, or 16, if you thought it affects /only/ the calculation of A. You might also have said ERROR if you thought that + and * are "reserved words" in Scheme and not usable as parameters, or if you thought that * by itself isn't a valid expression. (caaddr '((a b c d e) (f g h i j) (k l m n o))) Answer: K (cdr '((a b c d e) (f g h i j) (k l m n o))) ==> ((f g h i j) (k l m n o)) (cdr '((f g h i j) (k l m n o))) ==> ((k l m n o)) (car '((k l m n o))) ==> (k l m n o) (car '(k l m n o) ==> k The expected likely wrong answer here was ERROR. You could reach that conclusion in several ways. Among them are thinking that CAADDR means "first CAR then CAR then CDR then CDR" rather than what it really means, "CAR of CAR of CAR of CDR of CDR," or getting confused about the difference between ((K L M N O)), which is a one-element list whose element is a list, and (K L M N O), which is a five-element list. Scoring: One point each. If you put quotation marks in your answers, you lost only one point on questions 1 and 2 for that even if you did it more than once. 2. Box and pointer diagrams. (list (cons '(1) '(2)) (list '(1) '(2))) Answer: (((1) 2) ((1) (2))) ---->XX----------->X/ | | V V **----->X/ XX---->X/ | | | | V V V V X/ 2 X/ X/ | | | V V V 1 1 2 The two troublesome things here are understanding how to represent a one-element list (namely, as a single pair whose CAR is the one element and whose CDR is the empty list), and understanding that CONS just makes one pair, so it sticks the new element (1) at the front of the list (2), giving ((1) 2). The pair shown as ** above is the one made by the CONS call. (cons (cons 1 2) (append '(1) '(2))) Answer: ((1 . 2) 1 2) ---->XX------->XX----->X/ | | | V V V XX--->2 1 2 | V 1 The call to APPEND creates the list (1 2), made of the /elements/ of its argument lists; the outer call to CONS sticks one new element in front of that, namely the pair (1 . 2). Improper lists can be elements of lists! (And that doesn't make the overall list improper.) Scoring: One point per print form, one point per box and pointer diagram. 3. Normal and applicative order (define (foo x) 'done) (foo (foo)) a. Normal order. Since FOO is a defined (not primitive) procedure, the actual argument expression (FOO) in the outer call to FOO is /not/ evaluated; instead, the expression itself is substituted for the parameter, X, in the body of FOO. But there is no X in the body of FOO! So we never evaluate the subexpression (FOO), and so no error happens, and we return DONE, the value of the expression 'DONE in the body. This problem wasn't about notation, so we didn't take off for it, but the answer 'DONE (with the quotation mark) is wrong! It's just DONE. b. Applicative order. All the subexpressions of the outermost expression are evaluated before the procedure FOO is called. The value of FOO is the procedure; the value of (FOO) is the result of invoking FOO with no argument. So the result is ERROR (not enough arguments to FOO). c. (define (inc x) (+ x 1)) (+ (inc 3) (inc 3)) How many times is + called? + is a primitive, so the argument expressions [two of (INC 3)] are evaluated first thing even in normal order. But even if + were a defined procedure, it would still need to know the values of its arguments, so the argument expressions would be evaluated sooner or later. So, for both normal and applicative order, + is called three times, once in each call to INC and one in the outermost expression. So the answer is FALSE, it's not called more often in normal order. It /would/ be called a different number of times if a single argument appeared more than once in the body, or if an argument is never used at all (e.g., because of an IF or COND, or because it doesn't appear in the body at all, as in FOO above). So (SQUARE (INC 3)) would call + once in applicative order, but twice in normal order. Scoring: One point for each part. 4. Orders of growth. a. IF, FIRST, +, and = each take constant time. But COUNT, as the problem tells us, takes time Theta(N). So there are N recursive calls to ADDING (where N is the length of the sentence), each of which takes Theta(N) time. That makes THETA(N^2) altogether. The recursive call is part of the larger expression (+ (first sent) ) so after the recursive call returns, there's still some work to do, the addition. Therefore this procedure generates a RECURSIVE process. b. The recursive call in FOO is in the context (if ... ... ) Evaluating its second or third argument is the last thing the IF special form has to do, so there's no work left after the recursive call. Therefore FOO generates an ITERATIVE process. All the operations in FOO are constant time, and there are N recursive calls, so FOO is THETA(N) time. BAR doesn't have any recursive calls at all! It calls FOO twice, but FOO doesn't call BAR, and BAR doesn't call BAR. So BAR takes twice as long as FOO -- still THETA(N) time. At first sight, BAZ seems similar in its time requirements to BAR, because it calls FOO three times, which is only a constant factor slower than calling FOO once. This isn't true, though, because the /argument/ to FOO grows in each call! FOO calculates the sum of the numbers from 1 to N. This is N(N+1)/2, which is about (N^2)/2, which is Theta(N^2). So the first (innermost) call to FOO takes time Theta(N), but the next one takes time Theta(N^2), and produces an answer that's Theta((N^2)^2), i.e., N^4. Therefore the outermost call to FOO takes time THETA(N^4), and that's the answer! Scoring: One point per answer (two answers in (a) and four in (b)). 5. Higher order procedures. (a) make-map-adder (define (make-map-adder num) (lambda (sent) (every (lambda (x) (+ x num)) sent))) This problem is all about domains and ranges. The domain of MAKE-MAP-ADDER itself is numbers, so it has a parameter NUM; its range is procedures, so its body is a LAMBDA expression. What about the procedure created by that LAMBDA expression? Its domain and range are both sentences, so I gave it a formal parameter of SENT, and I used EVERY to "add that number to /each/ number in a sentence..." Only a few people made the very bad mistake of building the number 5 into the solution because it was used in the example we gave you. The example is just one example! Your program is supposed to work more generally. (b) make-map-maker. (define (make-map-maker fn) (lambda (num) (lambda (sent) (every (lambda (x) (+ x num)) sent)))) This time, the domain of MAKE-MAP-MAKER is functions (and we're told to call the argument FN). The range is /functions just like MAKE-MAP-ADDER/! So the (outermost) LAMBDA that forms the body of MAKE-MAP-MAKER has the same formal parameter [NUM] and body [(LAMBDA (SENT) ...)] as the procedure you wrote in part (a). Scoring: 4 points for each part, as follows: 4 correct. 3 trivial error. 2 has the idea. 1 has an idea. 0 other. "Has the idea" for this problem means getting the domains and ranges, but messing up the actual computation (i.e., the EVERY call). Here are a few specific fairly common wrong answers, mostly in the "has an idea" category: Part (a) 1pt - (lambda (sent) (lambda (arg) ... ; reversed 1pt - (every (lambda (x) (+ x num))) ; no lambda 1pt - using recursion correctly 0pt - Wrong recursion Part (b) 1pt - (lambda (x) (every (lambda (y) (fn x y)))) 6. Recursion. The judicious use of helper procedures is important here. (define (insert-multiples sent wd posn cnt) (if (= posn 0) (sentence (n-copies wd cnt) sent) (cons (first sent) (insert-multiples (bf sent) wd (- posn 1) cnt)))) (define (n-copies wd cnt) (if (= cnt 0) '() (sentence wd (n-copies wd (- cnt 1))))) It's possible to do it all in one big procedure, but the result is much messier: (define (insert-multiples sent wd posn cnt) ; don't do it this way! (cond ((= cnt 0) sent) ((= posn 0) (sentence wd (insert-multiples sent wd posn (- cnt 1)))) (else (sentence (first sent) (insert-multiples (bf sent) wd (- posn 1) cnt))))) As you can see, it's much harder to convince yourself that this procedure is correct -- is each clause correct, and are all the cases accounted for -- than in the first version. (For example, if the two base cases came in the other order, this would be wrong.) You were told that you can assume the position is legal, so there's no need for an (EMPTY? SENT) clause, but we didn't take off for it, provided that it returns the right value, namely, a sentence of just the inserted words -- not the empty sentence! A small error was to assume that the position and/or count have to be at least 1. The problem says "nonnegative," and there are perfectly good ways to handle the case position=0 (put the extra words at the front) or count=0 (just return the original sentence). A slightly different error was to think (incorrectly) that /position=1/ means to put the extra words in the front. Scoring: 6 correct. 5 trivial error. 3-4 has the idea. 1-2 has an idea. 0 other. Here are a few specific common wrong answers: 5pt - ((empty? sent) '()) as the first cond clause ; should return the inserted words 5pts - insertion off-by-one 5pts - "" instead of '() 4pts - (sent) or (wd) ; trying to invoke a sentence or a word 3pts - words after the repeated insertion breaks somehow 3pts - insert at the right place but not the right number of times 7. Data abstraction. (a) Ben has put PAPER in the CDR of the CAR of the structure, so this pair can't be a list. The constructor has to be something of the form (CONS (CONS PAPER) ) because the CDAR of the resulting structure will indeed be PAPER. The other two parts can be in either order, but the most natural thing is (define (make-game r p s) (cons (cons r p) s)) (define rock caar) (define paper cdar) ; You didn't have to say this one. (define scissors cdr) The important thing is that your constructor and your selectors have to be consistent with each other, so that (make-game (rock my-game) (paper my-game) (scissors my-game)) will always return the original MY-GAME. Some people invented data structures that were more complicated than necessary, but we accepted that as long as they were used consistently. (b) The second word of a sentence is its CADR, so Louis's code is best read as (list (cadr (car game)) (cadr (cadr game)) (cadr (caddr game))) Then we just turn the CADRs for the sentences into (FIRST (BF ...)) and turn the other selectors into ROCK, PAPER, and SCISSORS: (define (seconds game) (sentence (first (bf (rock game))) (first (bf (paper game))) (first (bf (scissors game))))) Some people misunderstood the question as asking you to rewrite Louis's code to follow Ben's change to PAPER and/or your own changes to the other procedures in part (a). But the question was very clear about the fact that we were asking you to fix the data abstraction violations, not to replace them with different data abstraction violations! Many people forgot to change LIST to SENTENCE; that was the most common mistake. Some people seemed to think that data abstraction means using any old synonym for CAR and/or CDR. The worst example was this: (list (paper (car game)) (paper (cadr game)) (paper (caddr game))) (CAR GAME) isn't a game (it's a sentence), so you can't use the selector PAPER on it! The selectors for sentences are FIRST, BF, LAST, BL. Scoring: In (a), one point for MAKE-GAME, one for ROCK, one for SCISSORS. In (b), one point for LIST to SENTENCE, one for CADR to FIRST of BF, one point for ROCK/PAPER/SCISSORS, one for getting them in the right order.