CS212 Spring 1997 Prelim 2 Answers

[1][2][3][4][5]

1.

a.

b.

(define-generic-function edible? (eater eaten))

(add-method edible? (method ((eater <thing>)(eaten <thing>)) #f))
(add-method edible? (method ((eater <animal>)(eaten <vegetable>)) #t))
(add-method edible? (method ((eater <venus-flytrap>)(eaten <fly>)) #t))

2.

a.

b.

(define-class <deque> <pair>)
; using a <triple> is a waste of space
; Another common error was to add slots, and not use head and tail

(define new-mutable-deque
        (method () `(()) ))
; or (list '()) or (cons '() '()) etc.
; see above for pictorial representation

(define insert-front!
        (method ((o <object>) (q <deque>))
                (bind ( (old (head q))
                        (new (make-triple `() o old)))
                  (set! (head q) new) 
                  (if (null? old) (set! (tail q) new))
                        (set! (prev old) new))))

(define extract-end!
        (method ((q <deque>))
                (bind ( (old (tail q)))
                (cond   ((null? old) (error "Empty DEQueue"))
                        ((null? (prev old)) 
                                (set! (head q `()))
                                (set! (tail q `()))
                                (val old))
                        (else:  (set! (next (prev old)) '())
                                (set! (tail q) (prev old))
                                (val old))))))
; Note that there are three cases listed:
; 1. There are no elements to extract because the queue is empty
; 2. The last element is also the first element, so we must set! (head q) also
; 3. Normal case

; This is how you would implement the other two functions:
(define insert-end!
        (method ((o <object>)(q <deque>))
                (bind ( (old (tail q))
                        (new (make-triple old o '())))
                  (set! (tail q) new)
                  (if (null? old) (set! (head q) new)
                        (set! (next old) new)))))

(define extract-front!
        (method ((q <deque>))
                (bind ( (old (head q)))
                (cond   ((null? old) (error "Empty DEQueue"))
                        ((null? (next old)) 
                                (set! (head q `()))
                                (set! (tail q `()))
                                (val old))
                        (else:  (set! (prev (next old)) '())
                                (set! (head q) (next old))
                                (val old))))))

3.

(define memoize
   (bind (((memory <list>) `())
          ((lookup <method>)
              (method (x (mem <list>))
                (cond ( ((null? mem) #f)
                        ((= x (head (head mem))) (head mem))
                        (else: (lookup x (tail mem))))))))
        (method ((f <function>))
            (method (x)
                (bind ((test (lookup x memory)))
                   (cond ((test (head (tail test)))
                          (else: (bind ((z (f x)))
                                   (set! memory (pair (pair x z) memory))
                                   z)))))))))
; corrected (4:45pm, 4/21/97)
; notice that it returns the pair (x (f x)) instead of just (f x)
; this is so (f x)=> #f is distinguished from #f
; common errors include: using append to set! the memory, using global state

4.

(bind ((y 3))
   (set! f (method (x) (+ x y)))
   (bind ((x 4))
      (set! g (method () (+ x y)))))

5.

a.
Yes, there is a major flaw. In her induction step, Prudence removes two students from the set B, and selects a third student (r). This implies that n+1 >= 3, yet in the base case, n=1. Clearly, 1+1 is not greater than or equal to 3. Thus the base case is not sufficient to support the induction step. In other words, transitivity does not work for a set of two elements.

b.
No. By logic and reasoning, the entire student body of a class graded on a curve cannot fail. Besides which, the TAs and the professor of this class are good teachers. If all students fail CS212, then that indicates that there is a failure on the part of the professor and the TAs, which contradicts the previous statement. Anyways, Prudence's theorem was invalid, so no conclusions can be drawn based on an invalid theorem.