CS 212 Spring 1997 Exam 1 Solutions

1. (17 pts)

a) 80
b) 40
c) (4)
d) stack overflow due to infinite loop
e) 9

2. (17 pts)

Prove by induction

Base Case:

(define theLst '(x)) where x is any <object>

(length theLst) = 1

( all-pairs theLst )

[{proc (lst <list>) (cond ((null? (tail lst)) '()) (else: (append (pair-with-list (head lst) (tail lst)) (all-pairs (tail lst)))))))} '(x) ]

(cond ((null? (tail '(x))) '()) (else: (append (pair-with-list (head '(x)) (tail '(x))) (all-pairs (tail '(x))))))))

(cond (#t '()) ... )

'()

Inductive Case:

Inductive Hypothesis - Assume that (all-pairs theLst) produces a list containing all the pairs for any theLst where

1 <= (length theLst) < n

Prove (all-pairs theLst) produces a list containing all the pairs for any theLst of length n

theLst looks like (en,...,e1)

(all-pairs theLst)

[{proc (lst <list>) (cond ((null? (tail lst)) '()) (else: (append (pair-with-list (head lst) (tail lst)) (all-pairs (tail lst))))))) } '(en ... e1)]

(cond ((null? (tail '(en ... e1))) '()) (else: (append (pair-with-list (head '(en ... e1)) (tail '(en ... e1))) (all-pairs (tail '(en ... e1))))))))

(cond (#f ...) (else: (append (pair-with-list (head '(en ... e1)) (tail '(en ... e1))) (all-pairs (tail '(en ... e1))))))))

(append (pair-with-list (head '(en ... e1)) (tail '(en ... e1))) (all-pairs (tail '(en ... e1))))

<by inductive hypothesis and assumption that pair-with-list works>

[{proc ((x <list>)(y <list>)) -appendBody-} ((en en-1) (en en-2) ... (en e1)) ((en-1 en-2) (en-1 en-3) ... (en-1 e1) (en-2 en-3) ... ... (e2 e1)) ]

<by assumption that append works>

((en en-1) (en en-2) ... (en e1) (en-1 en-2) (en-1 en-3) ... (en-1 e1) (en-2 en-3) ... ... (e2 e1))

3. (17 pts)

a)

pairs(n) = pairs(n-1) + (n-1)
         = pairs(n-2) + (n-2) + (n-1)
    ...  = pairs(1) + 1 + 2 + ... + (n-2) + (n-1)
pairs(1) = 0, pairs(n) = (n(n-1))/2

b)

The process generated by the all-pairs procedure is recursive. Each call to all-pairs generates a pending operation, which means that it uses more space the longer it runs. You can tell that it is recursive rather than iterative because after each recursive call to all-pairs, the function must still perform the append operation. If it were iterative, then a 'marker' parameter would be necessary to keep track of the iteration.

c)

for (l <list>) of length n 
    - pair-with-list is O(n)
    - length (pair-with-list x l) => n where x is any object
T(n) = T(n-1) + O(n-1) + O(n-1) + C
       ^all-pairs ^append  ^pair-with-list
        recursive call      (length (tail l)) => n-1
     = T(n-2) + 2O(n-2) + 2O(n-1) + C
 ... = T(1) + 2O(1) + 2O(2) + ... + 2O(n-1) + C          T(1) = C
     = 2O((n(n-1))/2) = O(n2)

4. (17 pts)

a)

(define (copy-list <function>)
    (method ((l <list>))
        (map (method (x) x) l)))

b)

(define (deriv-list <function>)
    (method ((l <list>) (acc <number>))
        (map (method (x) (deriv x acc)) l)))

c)

(define (map <function>)
    (method ((f <function>) (l <list>))
        (accum '() (method (x y) (cons (f x) y)) l)))

5. (10 pts)

Solution is missing...

6. (17 pts)

a)

(define (intersection-set <function>)
  (method ((s <list>) (t <list>))
    (cond ((null? s) '())
          ((element-of-set? (head s) t)
           (adjoin-set (head s) (intersection-set (tail s) t)))
          (else: (intersection-set (tail s) t)))))

b)

T(n) = T(n-1) + O(m) + C
     = T(n-2) + 2 O(m) + 2C
     ...
     = n O(m) + n C = O(mn).

T(n-1) is the recursive call,
O(m) is the call to element-of-set? and adjoin-set.

c)

(define (intersection-set <function>)
  (method ((s <list>) (t <list>))
    (cond ((or (null? s) (null? t)) '())
          ((< (head s) (head t)) (intersection-set (tail s) t))
          ((> (head s) (head t)) (intersection-set s (tail t)))
          (else: (adjoin-set (head s) (intersection-set (tail s) (tail t)))))))