CS212
Fall 1996
Prelim 1
Thursday, October 17, 1996

There are six (6) problems on this exam. Please check now that you have a complete exam booklet with seven (7) numbered pages. Write your name or id number on each page of the exam. Be sure to try all of the problems, as some are more difficult than others (i.e., don't waste a lot of time on a problem that is giving you a hard time -- move on to another problem and then return to it later).

This exam is closed book. No papers, books or notes may be used. However, we will provide you with a copy of the Dylan cheatsheet.

There is space provided to answer each question. You may request extra paper if necessary. Do not put any answers on the backs of pages (THEY WILL NOT BE GRADED), ask for an extra piece of paper if you need more space to answer a problem.

To help ensure that you don't accidentally miss any of the questions, we have marked those sections where an answer is requested with a --> in the right margin.

The staff reserves the right to ignore illegible answers. ``Pretty printing'' (proper indentation) of your code will aid in the grading process.

  1. (18 Points) For each of the following determine what value would be returned, or describe what error would occur. 
    1. (head (tail (head (tail '(5 (2 (6 3)) 4)))))

    2. (((method (x) x) 3) 4)

    3. (((method (car cdr) (method (x) (if x car cdr))) 1 2) #t)

    4. (define except 
  (method (test expr1 expr2) (if (not test) expr1 expr2)))
(except #t (/ 1 0) 3)
  2. (12 Points) This problem is concerned with the order of growth of functions. Consider the following code for reversing a list 
    (define reverse
  (method ((l < list >))
    (if (null? l)
        l
        (append (reverse (tail l)) (list (head l))))))
    1. Write a recurrence describing the running time of reverse as a function of the length of the list l. Just write the recurrence, don't try to solve it for a closed form (non-recursive definition). Remember to consider both the general case of T(n) and the case of T(0).

    2. What is the running time of reverse in ``Big-Oh'' notation, as a function of n, the length of the list l? Briefly justify your answer, you may use the recurrence from above or some other concise argument.

    3. What is the fastest possible running time, in ``Big-Oh'' notation, for a Dylan procedure that reverses a list? Briefly justify your answer.



  3. (16 Points) This problem is concerned with using induction and the substitution model to show that a procedure computes the specified result.

Consider the following code, which defines a tree and some operations on it: 

(define-class < tree >  (< object > ) (left < object > ) (right < object > ))

(define leaf?
  (method ((t < object > ))
    (not (instance? t < tree > ))))

(define count-leaves
  (method ((t < object > ))
    (if (leaf? t)
        1
        (+ (count-leaves (left t))
           (count-leaves (right t))))))

Consider a binary tree t, with left and right subtrees t.l and t.r respectively. The depth of t is defined to be one larger than the depth of its deeper subtree, that is depth(t) = 1 + max(depth(t.l), depth(t.r)). When t is a leaf node, meaning it has neither left nor right subtrees, its depth is 0.

Assume that for a binary tree t, represented using the class < tree > , that (leaf? t) is true only when t is a leaf node. Moreover assume that when (leaf? t) is false that (left t) = t.l and (right t) = t.r, that is that the accessors return the left and right subtrees respectively.

Using induction and the substitution model, prove that (count-leaves t) counts the number of leaf nodes in any tree t. We will break the question up into three parts: what you are inducting over, the induction hypothesis, and then the proof itself.

  1. What are you inducting over?


  2. Give a clear, concise statement of your induction hypothesis.


  3. Give an inductive proof that (count-leaves t) counts the number of leaf nodes in any tree t. Remember to have clear, separate base case and induction step. Use the induction hypothesis you gave above.





  1. (18 Points) This problem is concerned with writing a procedure that produces a list of running sums given a nonempty list of numbers. A running sum is the sum of the elements thus far in the list. For example, 
(running-sum '(1 2 3 4)) --> (1 3 6 10)

(running-sum '(7)) --> (7)

Write a recursive procedure to compute running-sum, which runs in time linear in the length of the list. Your answer may not use any helper procedures either by defining other top-level procedures or by having internal methods (in particular you cannot use bind-methods or any other way of creating a method inside a method).

As with this entire exam, you may not use set!.

  1. (18 Points) This problem concerns higher-order procedures for for composing functions. Recall that a higher-order procedure is one that takes a procedure as an argument or returns one as a value.

    The composition of two functions (or procedures) is simply the application of one followed by the other. Consider the following procedure: 

    (define compose
  (method ((f < function > ) (g < function > ))
    (method ((x < object > )) (f (g x)))))

    Thus ((compose f g) x) is equivalent to (f (g x)).

    This idea can be extended to a list of functions, where ((compose-list (list f g h)) x) is equivalent to (f (g (h x))). Write a procedure compose-list that takes a list of procedures and computes the composition of those procedures. For example, your procedure should behave as follows, 

    ((compose-list (list square inc)) 2) =9

((compose-list (list list head reverse)) '(1 2 3)) =(3)

((compose-list (list inc)) 3) =4

((compose-list '() 3)) =3

    Your procedure should run in time linear in the length of the list of functions. It should not use any helper procedures (including ones defined internally to compose-list) and should not use set!. You need not necessarily use the function compose defined above in your solution.

  2. (18 Points) This problem concerns generic functions. Consider the following two generic functions: 
    (define-generic-function f ((a  < object > )))

(add-method f (method ((a  < object > )) (print "apple")))

(add-method f (method ((a  < nurble > )) (print "lemon")))

(define-generic-function g ((b  < object > )))

(add-method g (method ((b  < glorp > )) (print "diamond")))

(add-method g (method ((b  < foo > )) (print "sapphire")))

(add-method g (method ((b  < object > )) (print "ruby")))

    Assume that the types < nurble > , < glorp > , < foo > and < bar > have been defined such that the following output is generated: 

    
(f (make  < glorp > )) = "apple"

(f (make  < foo > )) = "lemon"

(f (make  < bar > )) = "lemon"

(g (make  < bar > )) = "ruby"

    What are the definitions of the classes < nurble > , < glorp > , < foo > and < bar > that must have been defined to obtain this output?