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.