CS 212, Spring 1997 Exam 1

March 6, 1996

Problem	0	1	2	3	4	5	6	Total
Grade	2	17	17	17	17	10	17	95

(17 Points) For each of the following expressions determine what value would be returned by a Dylan interpreter, or describe what would happen if the expression is one that does not yield a value.

a) 
(bind ((x 10)(f +))
  (bind ((x (f x x))(y (f x x)))
    (f y y)))
=>

(bind ((y 20))
  (bind ((x y)
         (f (method (x) (+ x y))))
     (f x)))
=>

(head (tail (head (tail '(1 (2 (4)) 5)))))
=>

((method (f) (f f)) (method (g) (g g)))
=>

(+ ((method (x) x) 5) 4)
=>

(17 Points) In this problem we consider a procedure for computing all pairs of the elements in a list. For a list (e_n...e₁) we define the pairs to be a list containing all pairs (e_i, e_j), for i > j and 1 <= i,j <= n. We choose to represent each pair as a Dylan <pair>. For example, here are some lists with corresponding lists of pairs:

(a) -> () (a b) -> ((a b)) (a b c) -> ((a b) (a c) (b c))

The following procedure is purported to compute the unordered pairs for a given list, lst:
```
(define all-pairs
  (method ((lst <list>))
    (cond
      ((null? (cdr lst)) ())
      ((null? (cddr lst)) (list lst))
      (else (append (pair-with-list (car lst) (cdr lst))
                    (all-pairs (cdr lst)))))))
```
where cddr is defined as
```
(define cddr (compose cdr cdr))

(define compose
  (method ((f <function>) (g <function>))
    (method ((x (<object>))) (f (g x))))) 
```
All-pairs makes use of the helper procedure
```
(define pair-with-list 
  (method ((elt <object>) (lst <list>))
    (if (null? lst)
      ()
      (cons (list elt (car lst))
            (pair-with-list elt (cdr lst))))))
```
Prove by induction that (all-pairs lst) produces a list containing all the pairs for any lst of length n>1, using the above definition of pairs. You may assume that
```
(pair-with-list x (e_n ... e₁))
```
returns the list ((x e_n) ... (x e₁)), for any length n. You may further assume that (append l1 l2) correctly forms the concatenation of the lists l1 and l2, for any length lists.
(17 Points) The following procedure map was introduced in lecture:
```
(define map 
  (method ((f <function>) (lst <list>))
    (if (null? lst)
      ()
      (cons (f (car lst)) (map f (cdr lst))))))
```
1. Write a procedure copy-list that uses map to copy a list.
2. Write a procedure deriv-list that uses map to apply the procedure deriv to each element of a list. Recall from lecture that deriv takes two arguments, for example (deriv square .001) returns the derivative of the square procedure computed to an accuracy of .001:
```
(define (deriv <function>)
  (method ((f <function>) (dx <number>))
    (method ((x <number>)) 
      (/ (- (f (+ x dx))
            (f x))
         dx))))
```
  Deriv-list should also take two arguments: the list and the accuracy.
3. Now consider the procedure
```
(define accumulate 
(method ((base <object>) (combiner <function>) (lst <list>))
(if (null? lst)
base
(combiner (car lst)
(accumulate base combiner (cdr lst))))))
```
  Rewrite the map procedure in terms of accumulate (i.e., define the map procedure using accumulate).
(17 Points) List structures in Dylan are printed as sequences of elements, enclosed in parentheses. If the final element of a given list structure is not itself a list, this is denoted by printing a dot before that element. For example here is how several different expressions would be printed:
```
(cons 1 (cons 2 (cons 3 ()))) -> (1 2 3)
(list 1 2 3) -> (1 2 3)
(cons 1 (cons 2 3)) -> (1 2 . 3)
(list (cons 1 2) 3 (list 4 5)) -> ((1 . 2) 3 (4 5))
```
1. Draw the box and pointer diagram corresponding to
```
(1 2 . 3)
```
2. Draw the box and pointer diagram corresponding to
```
((1 . 2) 3 (4 5))
```
(10 Points) Consider again the code from problem 2 for computing all the unordered pairs of the elements in a list.
```
(define all-pairs
  (method ((lst <list>))
    (cond
      ((null? (cdr lst)) ())
      ((null? (cddr lst)) (list lst))
      (else: (append (pair-with-list (car lst) (cdr lst))
                    (all-pairs (cdr lst)))))))
```
making use of the helper procedure
```
(define pair-with-list 
  (method ((elt <object>) (lst <list>))
    (if (null? lst)
      ()
      (cons (list elt (car lst))
            (pair-with-list elt (cdr lst))))))
```
1. How many unordered pairs are there for a list of length n? Briefly justify your answer.
2. Is the process generated by the all-pairs procedure iterative or recursive?
3. What is the order of growth of the running time of the all-pairs procedure as a function of the length n of lst? Recall that the append procedure requires time proportional to the length of its first argument; that is, (append l1 l2) takes O(n) time where n is then length of l1. Briefly justify your answer.
(17 Points) In this problem you will be implementing sets of numbers in terms of lists. For the purposes of this problem, the operations element-of-set?, adjoin-set, and intersection-set are defined on sets, and must obey the following contract:
1. Write the procedure intersection-set for this implementation of sets as unordered lists.
2. What is the order of growth of your procedure as a function of the sizes of the two sets, m and n? Briefly justify your answer.
3. Now we consider re-implementing sets as ordered lists, using the following definitions
```
(define adjoin-set
  (method ((x <object>) (set <>))
    (cond ((nul? set) (list x))
          ((= x (car set)) set)
          ((< x (car set)) (cons x set))
          (else: (cons (car set) (adjoin-set x (cdr set)))))))

(define element-of-set?
  (method ((x <object>) (set <list>))
  (cond ((null? set) \#f)
        ((= x (car set)) \#t)
        ((< x (car set)) #f) 
        (else: (element-of-set? x (cdr set))))))
```
  Write a linear time implementation of intersection-set given this new ordered representation of sets (i.e., for two sets of length m and n your procedure should run in time O(m+n).)