Summer 1995 CS 61A Midterm #1 Solutions Question 1 [5 points total]: Scheme Expressions =============================================== > (define cs61a-is-fun 1) cs61a-is-fun > (define nothing (lambda () (lambda () 0))) nothing > (* (+ 2 5) (+ 3 6)) 63 > (nothing) PROCEDURE Evaluating the nothing procedure (which takes no arguments) returns the result of evaluating (lambda () 0), i.e., a procedure object. > ((nothing)) 0 Applying the procedure object from above simply returns 0. > (((nothing))) ERROR Since ((nothing)) returns 0, we'd be trying to apply 0 as a procedure. > ((lambda (x) (x x)) (lambda (y) (+ 10 20))) 30 The second lambda expression is applied to itself as its argument, i.e., y is bound to the procedure object obtained by evaluating (lambda (y) (+ 10 20)). But y is ignored since it doesn't appear in the body, (+ 10 20). > (if (< 2 1) (+ 6 5) (else (* 4 3))) ERROR Since "else" is not part of the if special form syntax, the Scheme interpreter attempts to find a binding for the name "else" and gets an unbound variable error. > ((lambda (f x) (if (f x) f x)) even? 10) PROCEDURE The procedure denoted by the lambda expression is applied to even? and 10. Since 10 is even, f is returned, and f is bound to the procedure even? > (let ((cs61a-is-fun (+))) (+ cs61a-is-fun 2)) 2 cs61a-is-fun is bound to the result of adding no numbers to 0, and adding this to 2 gives 2. > (if (and (= cs61a-is-fun 1) (> 1000 0)) cs61a-is-fun (2 + 1)) 1 cs61a-is-fun is bound to 1 (we're no longer in the scope of the above let expression), and 1000 > 0, so cs61a-is-fun is evaluated, returning 1. Evaluating (2 + 1) would return an error, but it is never evaluated. SCORING: 0.5 points per correct response. Question 2 [4 points total]: Determining Order of Growth ======================================================== A. (define (foo n) (cond ((= n 0) 1) ((even? n) (/ n 2)) (else (* n (foo (-1+ n)))))) CONSTANT If n is even, the procedure returns immediately. If n is odd, it calls itself again with n-1, an even number. Thus, foo is only called at most twice for any value of n. B. (define (bar n) (cond ((= n 0) 1) ((even? n) (+ (bar (/ n 2)) (bar (/ n 2)))) (else (bar (-1+ n))))) LINEAR Only a small fraction of the class answered this question correctly. The bar function computes the largest power of 2 less than or equal to n. Drawing the tree for varying values of n shows that the number of nodes grows linearly with the size of n. Note that if n is odd, then bar is called with n-1. If n is even, bar is called TWICE with n/2. SCORING: 2 points per part. No partial credit if order of growth was incorrect. Question 3 [7 points total]: Guessing Game ========================================== A. (3 pts) Completing the code: (define (guess-number) (define (helper lower-bound guess upper-bound) (let ((result-code (how-is-this-guess? guess))) (cond ((or (= lower-bound upper-bound) (= result-code 1)) guess) ((= result-code 2) (helper (1+ guess) (newguess guess upper-bound) upper-bound)) ((= result-code 3) (helper lower-bound (newguess guess lower-bound) (-1+ guess)))))) (helper 0 0 1000)) If the guess is correct (first test in the cond), then the guess is just returned. If the guess is too low, then helper is called again, with the new lower-bound as guess+1, the new guess as guess+1, and the new upper-bound unchanged. SCORING: -0.5 pts for missing parenthesis in first blank. -1 pt for extra parens around upper-bound in 2nd blank. -2 pts for incorrect call to helper in 2nd blank. B. (1 pt) Recursive or iterative? ITERATIVE C. (1 pt) Order of growth LINEAR For different values of the secret number, the algorithm will take on average n/2 steps to find the guess (since it will count up from 0 by 1 to the secret number). This is linear growth. D. (1 pt) Modified starting guess LINEAR The algorithm now takes n/4 steps on average, since it now starts in the middle of the range from 0 to n. This is still linear growth. E. (1 pt) New newguess algorithm LOGARITHMIC Now newguess generates new guesses halfway between the old guess and either the upper or lower bound. This effectively halves the range of possible guesses at each iteration. SCORING: No partial credit for parts B through E. If your answer was incorrect but was consistent with incorrect code in part A or previously incorrect answers, then you still received credit. Question 4 [13 points total]: Improving "improve" ================================================= A. (5 pts) General-improve procedure (define (general-improve f lower-bound guess) (define (iter n) (let ((candidate (f n))) (cond ((> candidate guess) candidate) (else (iter (+ n 1)))))) (iter lower-bound)) SCORING: This part could be solved just by pattern-matching with section 1.3.1 of the textbook. Some people let candidate be just f rather than (f guess), and others forgot to call iter after defining it. -2 pts each for either error. Incorrect parentheses for the let expression was -1 pt. B. (5 pts) Create-improver procedure (define (create-improver f lower-bound) (lambda (guess) (general-improve f lower-bound guess))) OR (define (create-improver f lower-bound) (lambda (guess) (define (iter n) (let ((candidate (f n))) (cond ((> candidate guess) candidate) (else (iter (+ n 1)))))) (iter lower-bound))) Since the body of create-improver is a lambda expression, applying create-improver returns a procedure object. This new procedure takes one argument, guess, and returns an improved guess. It iteratively applies the function f to integers starting from lower-bound until it obtains a candidate value larger than guess. It then returns that candidate. SCORING: Most people either got this part either completely correct or mostly wrong, so there wasn't much partial credit to give. Most people who got partial credit got only 1 point, usually for returning a procedure taking one argument. C. (3 pts) (define improve (create-improver (lambda (n) (+ (square n) n 41)) 100)) (define improve2 (create-improver (lambda (n) (- (expt 2 n) 1)) 2)) The following are also acceptable: (define (improve guess) ((create-improver (lambda (n) (+ (square n) n 41)) 100) guess)) (define (improve2 guess) ((create-improver (lambda (n) (- (expt 2 n) 1)) 2) guess)) SCORING: The most common error was mixing the above two forms. Many people wrote: (define (improve guess) (create-improver (lambda (n) (+ (square n) n 41)) 100)) But this means that a call to improve returns a procedure object and ignores guess. -2 pts for this error. Some people forgot to include a define, and this was -0.5 pts.