MIDTERM 1 SOLUTIONS
QUESTION 1: What will Scheme print?
6 points, 1 point per expression
> (se (last '(cal)) (butlast '(golden)) '(bears))
(cal bears)
First, note that (last '(cal)) returns the word cal. Second, note that
(butlast '(golden)) returns the empty sentence. So combining the three
arguments to se together, the return value is the sentence (cal bears)
> (every (lambda (x) (keep #t x)) '(hi there))
ERROR
The error is due to the fact that #t is not a predicate, in fact, it's not
even a procedure. The first argument to keep must always be a predicate.
> ((lambda (x) (x 5)) (lambda (y) (+ y 2)))
7
Evaluating (lambda (y) (+ y 2)) gives a procedure that adds 2 to its
argument. We take this procedure and replace the x in the body of (lambda
(x) (x 5)) with it, and then we evaluate the body. This amounts to
computing the sum of 5 and 2, which is 7.
> (if 'kevin 'gap ramesh)
gap
Remember that in Scheme everything is considered true except for #f. The
expression kevin evaluates to the word kevin, which is considered true.
Therefore the return value is given by the evaluation of gap, which is the
word gap. Note that the expression ramesh is not evaluated (if it had been
evaluated, we would have gotten an unbound variable error). This is
because if is a special form.
> (let ((bf first) (first bf))
(word (bf 'zidane) (first 'redcard)))
zedcard
Within the body of the let, bf is bound to the first function, and first
is bound to the bf function (to see why, expand the let expression into
its full lambda form). So in the body of the let, (bf zidane) returns the
word z, and (first redcard) returns the word edcard. These are combined
into the word zedcard.
> (lambda (x) *)
PROCEDURE
Any valid call to lambda always returns a procedure.
No partial credit.
QUESTION 2: Order of growth
4 points, 2 points per question
Order of growth in time = Theta(n^2)
Note that the first procedure call is (helper 0), wherein x is bound to 0.
At each step, we increment x by 1, and we keep doing this until x is equal
to the square of n, at which point we halt and return. Each recursive call
takes constant time, and there are n^2 recursive calls, so in total we
require Theta(n^2) time.
Order of growth in space = Theta(n^2)
The recursive cases of the helper procedure alternate between those of the
form (helper (+ x 1)) and those of the form (+ 4 (helper (+ x 1))). In the
latter cases, the interpreter must remember to add 4 to the result of the
recursive call. In the former cases, the interpreter does not need to
remember to do anything after the recursive call is finished. Since the
latter cases make up half of all of the cases, we require Theta((1/2)n^2)
space, which simplifies to Theta(n^2).
No partial credit.
QUESTION 3: Higher order functions.
4 points
Here is one solution:
(define (negevens sent)
(keep even? (every (lambda (x) (* -1 x)) sent)))
Here is another possible solution:
(define (negevens sent)
(every (lambda (x) (* -1 x)) (keep even? sent)))
These are basically the only two ways to do this problem. There's probably
a tricky way to do it with accumulate, but there's no point in making it
more complicated than it needs to be.
2 points for doing keep and/or every but the result is not exactly right.
1 point for doing keep and/or every and the procedure will result in error
in one of them.
QUESTION 4: Data abstraction
7 points, 3 points for the box-and-pointer diagram, 2 points per selector
The box-and-pointer-diagram looks like this:
+-+-+ +-+-+ +-+-+
|||-+->|||-+->|||/|
+++-+ +++-+ +++-+
| | |
V | V
12345678 | +-+-+ +-+-+ +-+-+
| |||-+->|||-+->|||/|
V +++-+ +++-+ +++-+
+-+-+ | | |
||||| V V V
+++++ 75 85 95
| |
V V
john doe
1 point for first level list, +1 point for cons pair, +1 point for the
grade list.
Here are the selectors we wanted you to write:
(define (last-name student-entry)
(cdadr student-entry))
All or nothing. No partial credit.
[We will, of course, accept (cdr (cadr student-entry)) or (cdr (car (cdr
student-entry))), etc.]
(define (exam-grade student-entry)
(caddr (caddr student-entry)))
1 point if order of CARs and CDRs reversed.
QUESTION 5: count-big-jumps
9 points
Here is one possible solution:
(define (count-big-jumps sent jump)
(define (big-jump? x y)
(> (abs (- x y))))
(define (helper sent)
(cond ((empty? sent) 0)
((empty? (bf sent)) 0)
((big-jump? (first sent) (first (bf sent)))
(+ 1 (count-big-jumps (bf sent) jump)))
(else
(count-big-jumps (bf sent) jump))))
(helper sent))
8 points: "off-by-one" errors.
7 points: minor errors, such as (- (abs (first sent)) (abs (first (bf
sent)))), etc.
6: slightly worse errors, such as DAVs, etc.
4 or below: did not work at all.
QUESTION 6: first-bf-func
9 points
Here is one possible solution:
(define (compose f g)
(lambda (x) (f (g x))))
(define (first-bf-func sent)
(cond ((empty? sent) (lambda (x) x))
((equal? (first sent) first)
(compose first (first-bf-sent (bf sent))))
(else
(compose bf (first-bf-sent (bf sent))))))
Or you could have gone down the sentence in the opposite direction. If you
did it that way, you would have also had to reverse the order in which you
composed the functions.
(define (first-bf-func sent)
(cond ((empty? sent) (lambda (x) x))
((equal? (last sent) first)
(compose (first-bf-sent (bl sent)) first))
(else
(compose (first-bf-sent (bl sent)) bf))))
It was not necessary to define compose as a helper procedure. For example,
in the solution above, instead of writing
(compose (first-bf-sent (bl sent)) bf),
you could have written
(lambda (x) ((first-bf-sent (bl sent)) (bf x))).
7 points: applying the procedures backwards, other minor errors.
6 points: composition problems, using words as procedures, etc.
2 points: miscellaneous serious errors.
0 points: a procedure with incorrect domain/range.
In a few very rare cases (about 3 cases), I gave out 1 or 2 points to
procedures with incorrect domain/range, but that had noble attempts to
return a procedure. If you did even try to return a procedure, you got 0
points.