CS61A Midterm 1 Solutions Summer 2002 The midterm consited of 8 questions, each worth 5 points. Question 1: Applicative and Normal Order Part A ------ Normal: 7 Applicative: 3 (define (greg x y z) (z (* x y))) (greg 3 (* 2 2) (lambda (x) (* x x x))) In normal order, we first substitute the argument expressions into the body, delaying their evaluation. So GREG's three arguments are substituted into the body giving us: body => (z (* x y)) substitution => ((lambda (x) (* x x x)) (* 3 (* 2 2))) Next, the argument expression of (lambda (x) (* x x x)) is substi- tuted into its body, obtaining: (* (* 3 (* 2 2)) (* 3 (* 2 2)) (* 3 (* 2 2))) 7 Calls to *. In applicative order, all arguments are evaluated first, so we get (greg 3 4 (lambda (x) (* x x x))) At this point, one call to * has occurred: (* 2 2) => 4. Having evaluated all arguments, their values are then plugged into the body of GREG. body => (z (* x y)) substitution => ((lambda (x) (* x x x)) (* 3 4)) Next we evaluate the argument to the lambda function. This results in another call to *: (* 3 4) => 12. We then substitute 12 in for X into the body of the lambda function. (* 12 12 12) This results in a third call to *. Part B ------ Applicative: 2 Normal: 3 The LET is just a function call, so the expression can be interpreted as: ((lambda (a b) (if (= a b) (* a b) b)) (* 2 3) (* 6 7)) In applicative order (* 2 3) and (* 6 7) are computed when the arguments are evaluated. That makes 2 calls to '*'. In normal order (* 2 3) and (* 6 7) are computed when they're passed as arguments to =. Additionally (* 6 7) is evaluated again as the return value of the IF. Question 2: Functions (define (jeffified? a b c) (OR (equal? a b) (pair? c) (AND (odd? (+ a b c)) (equal? (- a b) -2)))) Grading ------- Two points were given for correct use of AND and OR. A common mistake was (and ((equal? a b) ... Two points for correct logic -- the new definition of JEFFIFIED? behaves like the original one. One point for a succinct solution. Some solutions were not fully simplified: (or #t (equal? a b) ... Question 3: Recursion There were many possible solutions to this problem. Here's the most common one: (define (running-total sent) (running-helper (first sent) (bf sent))) (define (running-helper total sent) (if (empty? sent) total (se total (running-helper (+ total (first sent)) (bf sent))))) An interesting solution was: (define (running-total sent) (if (empty? (bf sent)) sent (se (first sent) (running-total (se (+ (first sent) (first (bf sent))) (bf (bf sent))))))) The second solution was more tricky to get right. Because you're reaching for the first and second elements of SENT, the base case has to be when the SENT contains just one element. Also, in the recursive case, you must call BF twice on the sentence in order for it to shrink in size. Grading ------- One point was given for a solution that was recursive. Non-recursive solutions received no points. Two points were given for a solution that did *something* to the argument sentence (even if it's not the right *something*). Solutions that generated the running total in the wrong order, for instance, received these two points + 1 for having a recursive solution. Two points were given for a solution that did the right *something*, that is, solutions that actually produced the correct return value. Points were deducted for solutions that would crash or enter an infinite loop depending on the severity of the mistake. Question 4: Let Part A ------ The answer was 18, and it was worth two points. One point was given for 16 or 20. Part B ------ ((lambda (x y) ((lambda (x y) ((lambda (x) (+ x y)) (+ x 7))) 5 (+ x 3))) 3 4) Grading ------- One point was given for having the right idea: nested LAMBDAs. Solutions without nested LAMBDAs received no credit. One point was given for correct argument order -- each LAMBDA correctly matched its argument(s). One point was given for correctly calling the LAMBDAs with the arguments (ie, two open parenthesis). Common mistakes included placing the LAMBDAs "inside out": ((lambda (x y) ((lambda (x y) ((lambda (x) (+ x y)) 3 4) ) 5 (+ x 3)) ) (+ x 7)) Or evaluating some of the arguments beforehand: ((lambda (x y) ((lambda (x y) ((lambda (x) (+ x y)) 12) ) 5 6) ) 3 4) Question 5: Lists Part A ------ Jane is correct. As implemented, ERWINS-LIST? would crash when given something that is not a list instead of returning #t. It should check if its argument is a pair before trying to take its CDR. Part B ------ All that's missing is a check for PAIR? (define (erwins-list? l) (or (null? l) (and (pair? l) (erwins-list? (cdr l))))) Many people had something like this: (define (erwins-list? l) (and (pair? l) (or (null? l) (erwins-list? (cdr l))))) While this definition of ERWINS-LIST? no longer crashes on a non-list, it always returns #f. This is because the arguments to AND cannot both be true since something that is a pair (has a CAR and a CDR) *cannot* also be null. The null list is *not* a pair. Grading ------- One point was awarded for Part A -- all or nothing. Correct solutions needed to state that ERWINS-LIST? crashes. Three points were awarded for Part B. If you had the PAIR? check somewhere in Part B, you got at least one point. Question 6: Higher Order Procs Part A ------ The expression (add-one zero) returns a procedure that when called with one argument -- which can be anything -- returns the identity function, which is the zero Kurt numeral. Part B ----- By far the most common solution was: (define (show-kurt-val num) (if (equal? num zero) 0 (+ 1 (show-kurt-val (num 'dummy))))) The key is to realize that the procedure representing Kurt number N will return Kurt number N - 1 when called with a single, arbitrary argument. All that's left is to compare the argument NUM to zero. Grading ------- Part A was worth one point. Half a point was given for saying the return value was a procedure, but failing to describe it further. Common wrong answers included saying that (add-one zero) returns the zero Kurt numeral. This is wrong because ((add-one zero) 'anything) returns the zero Kurt numeral; (add-one zero) returns the Kurt numeral representing one. Part B was worth 4 points that were split (roughly) between the base case and the recursive case. Solutions using CAR and CDR received no credit. Question 7: Abstraction This was the hardest question on the exam, and most people did not get it (on the individual portion). func-1: cdr func-2: null? func-3: car func-4: cons func-5: map func-6: filter All of these functions implement the "list" datatype. Saying "cons" or "pair" also was fine. One way to approach this problem is to notice that FUNC-5 and FUNC-6 are recursive. This implies that they're processing the mystery datatype that we've implemented. Constructors and selectors generally are not recursive. FUNC-1, FUNC-2 and FUNC-3 look an awful lot alike, so we'll assume that they're all doing basically the same thing, and we'll come back to them later. FUNC-4 is the key. It takes two arguments and returns one -- which is exactly what a constructor does: combines multiple elements into one. If this is our constructor, then we can see how FUNC-3 returns the P (the car) and FUNC-1 returns the Q (the cdr). The hardest part is to figure out the purpose of FUNC-2. A lot of people started down the wrong road when they assumed it is the NOT function. The key is to look at the base cases of FUNC-5 and FUNC-6. The base case is hit when #f is encountered, which means the lists we're making must end in #f, just like regular Scheme lists must end in '(). Grading ------- This really was an all or nothing problem. Little partial credit could be given. FUNC-1 through 4 were each worth 1/2 point. FUNC-5 and FUNC-6 were worth 1 point. And Part A was worth 1 point. Question 8: Orders of Growth Part A - Big-Theta (n) Part B - Big-Theta (n) Part C - Big-Theta (3^n) Part D - Big-Theta (n^2) A lot of people though Part B was Big-Theta (n^3), but this only happens if a function issues three *recursive* calls or processes something in three dimensions: carries out a linear process on every iteration of a linear process on every iteration of a linear process. The repetition was not a typo. I mean something like: (map (lambda (a) (map (lambda (b) (map (lambda (c) (foo c)) b)) a)) list) Grading ------- Two points were awarded for the first right answer; one point for every right answer after that.