Prelim 1 Fall 1996 Solutions

1. 1. '(6 3)
   2. error: first element in combination must eval to a function
   3. 1
   4. error: divide by zero

2. 1.  T(0) = c, T(n) = T(n-1) + O(n) + ci 

   2. O(n²)
   3. O(n²)
3. (a) Induction is over the depth of the tree, depth(t)
   (b) Assume that for any tree s of depth m <= d that (count-leaves s) counts the number of leaf nodes in s
   (c) Base Case: depth(t) = 0, i.e., t is a leaf
   

   (count-leaves t)
   (if (leaf? t) 1 ...)
   

   which is 1 because t is a leaf, as stated above.

   Induction:
   Assume t is a tree of depth d+1 and that for any tree s of depth <= d that (count-leaves s) is the number of leaves in s.
   

   (count-leaves t)
   (if (leaf? t) 1 (+ (count-leaves (left t)) (count-leaves (right t))))
   (+ (count-leaves (left t)) (count-leaves (right t)))
   

   by substitution, because t cannot be a leaf (d+1 is strictly greater than 1).

   We also know that (left t) and (right t) are of depth at most d-1 by the definition of trees. Thus by the induction hypothesis, the sum (+ (count-leaves (left t)) (count-leaves (right t))) is the total number of leaves in t.

4. (define (running-sum <function>)
     (method ((l <list>)
       (cond ((null? l) (error "Empty List!"))
             ((null? (tail l)) l)
             (else: (pair (head l)
                          (running-sum 
                             (pair (+ (first l) (second l))
                                   (tail (tail l)))))))))
   

5. (define (compose-list <function>)
     (method ((l <list>))
       (if (null? l) 
           (method (x) x)
           (method (x) ((head l) ((compose-list (tail l)) x))))))
   

6. (define-class <glorp> (<object>))
   (define-class <nurble> (<object>))
   (define-class <foo> (<nurble>))
   (define-class <bar> (<nurble>))