Chris Pollett>Old Classes>PIC 15, Fall 1999>Practice Midterm

1. Define the following terms with an example:
   1. normal order evaluation

      
      ANS: evaluation order in which one expands the body of a function first filling 
      in the as yet to be evaluated arguments. One then executes the function and 
      evaluate arguments only as needed. Ex: One would evaluate (square (+ 6 3))
      first by expanding square to (* (+ 6 3) (+6 3)) then getting (* 9 9) and finally
      81.
      

   2. tree recursion

      
      ANS: recursive process where at any stage of evaluation might spawn
      one or more subinstances of the problem. Ex: Calculating the Fibonnaci 
      numbers without using the closed form expression. These numbers are: 
      1 1 2 3 5 8 ...
      Each number is the sum of the previous two and we define f(0)=1 and f(1)=1.
      The nth Fibonnaci number could be calculated using f(n) = f(n-1) +f(n-2)
      and the base cases. i.e., we spawn two subinstances of the problem
      at any stage. If we looked at the graph of calls used in calculating
      f(n) it would look like a tree.
      

   3. message passing

      
      ANS: The use of "intelligent object" which when passed a message can
      perform on themselves requested function.
      
      Ex: Below is code for a complex number object using rectangular coordinates:
      
      (define (make-from-real-imag x y)
      	(define (dispatch op)
      		(cond ((eq? op 'real-part) x)
      			((eq? op 'imag-part) y)
      			((eq? op 'magnitude)
      				(sqrt (+ (square x) (square y)))
      			((eq? op 'angle)
      				(atan x y))
      			(else
      				(error "unknown method MAKE-FROM-REAL-IMAG" op))			
      		)
      	)
      dispatch
      )
      
      ;To get the real part of an object of this type could define:
      
      (define (real-part x) (x 'real-part))
      

2. Prove that 1+2+3 + ...+ n is an element of Theta(n^2) and that 1+2+2^2+2^3+...+2^n is an element of Theta(2^n).

   
   
   ANS: 1+2+3+ + n = n(n+1)/2. To see this notice we can make the following
   set of n/2 pairs. 1+n, 2 + n-1, 3 + n-2,... Each of these sums to n+1.
   Adding them together gives the sum on the left.
   
   Then notice n^2/2 <= n(n+1)/2 <= n^2 for all n>=N=1 so this will be in 
   Theta(n^2).
   
   For the second question notice 1+2+2^2+2^3+...+2^n = (2-1)(1+2+2^2+2^3+...+2^n)
   =2^{n+1}-1 and we have 2^n <= 2^{n+1}-1 <= 2*2^n for all n>=N=1.
   So this will be Theta(2^n).
   
       
   

3. Rewrite the following built-in functions by filling in the questioned-marked area with code.

   
   Q:	(define (map p sequence)
   		(accumulate (lambda (x y) [??]) nil sequence))
   
   ANS:
   	(define (map p sequence)
   		(accumulate (lambda (x y) (cons (p x) y)) nil sequence))
   
   Q:	(define (append seq1 seq2)
   		(accumulate cons [??] [??] ))	
   ANS:
   	(define (append seq1 seq2)
   		(accumulate cons seq2 seq1 ))	
   
   
   

4. Suppose we implement binary search trees so that the following three selectors project out the value at the root, the left branch and the the right branch of the tree:

   
   (define (entry tree) (car tree))
   (define (left-branch tree) (cadr tree))
   (define (right-branch tree) (caddr tree))
   
   

   1. How would the following tree be represented in this format?

         6
       3   7
      2 4    8
      
      ANS: (6  (3  (2 () ()) (4 () ()) )   (7 ()  (8 () ()) ) )
      
      

   2. Show an implementation of the predicate element-of-set? which checks if x is in the binary search tree called set.

      
      
      (define (element-of-set? x set)
      	(cond ((null? set) false)
      	      ((= x (entry set)) true)
      	      ((< x (entry set))
      			(element-of-set? x (left-branch set)))
      	      ((> x (entry set))
      			(element-of-set? x (right-branch set)))
      	)
      )	
      
      
      

5. Recall the complex numbers package that was discussed in class. Explain in detail how the following function produces a complex number from two real numbers:

   
   (define (make-from-real-imag x y)
   	((get 'make-from-real-imag 'rectangular) x y))
   
   
   ANS: make-from-real-imag takes x and y then calls the functions 
   (get 'make-from-real-imag 'rectangular). This function looks up in
   our complex number package's table the row whose first two columns are
    'make-from-real-imag and 'rectangular. It then returns the function listed
   in the third column. This function when given two inputs returns a 
   complex number represented using rectangular
   coordinates. This function is then applied to x and y. In this case,
   what it does is just (cons x y) and return the resulting list.