6.001 Quiz Review – March 5, 2003

 

RI: Konrad Tollmar

 

-         Wed., Oct 9th, from 7:30-9:30pm.

-         4-270 / 4-370.

-         Closed Book / one sheet of notes

-          Quiz 1 cover: Basic Scheme, Substitution model, Recursive and iterative procedures, order of growth, types and high-order procedures, pairs and lists, higher-order list procedures, trees, and symbols.

 

1. Warm-up

                                Value               Type

(define (three) 3)

three

(three)

(define four 4)

four

(four)

(+ (three) four)

 

(define (add-x x)

           (lambda (y) (+ y x)))

(define add-10 (add-x 10))

(add-10 5)

 

2. Procedures

Given the procedure,

 

(define apply-to-3-and-4

   (lambda (p) (p 3 4)))

 

What choices for <exp> in a combination of the form (apply-to-3-and-4 <exp>) will cause the following numbers to be returned?

 

a. 7
b. 1
c. 2
d. 3
e. 4

 

3. Recursive procedures

Someone, by misstake i guess, redefined the standard + and – procedures (among many other procedures).

 

a. Write a new recursive add procedures by only using  the =,  inc and dec procedures.

b. Write a new iterative subtract procedures by only using  the =,  inc and dec procedures.

 

4. Higher-order procedure

a. In question 1, we considered the procedure apply-to-3-and-4. Suppose we want to construct a new procedure, create-apply-to-x-and-y that can build procedures like apply-to-3-and-4. Using this new procedure, we could define apply-to-3-and-4 as follows: 

 
(define apply-to-3-and-4 (create-apply-to-x-and-y 3 4))
 



Write the procedure create-apply-to-x-and-y. 



 



b. The procedure sum is a higher-order procedure that compute the sum of a sequence of term in the interval from a to b with the increment next.  Please fill in the missing part INSERT1 and INSERT2.



 



(define (sum term a next b)



  (if (INSERT1)



      0



      (+ INSERT2



            (sum term (next a) next b))))



 



c.  Use sum to create an expression the compute the summary of squares 

between 1 and 10.



 



5. List procedure



 



a. Write a recursive process version of a procedure called remove that takes a number and a list and returns a new version of the list where that number is no longer an element. 
(not using filter).
 
(remove 1 (list 1 2 3 1 4 5 1 6)) 
=> (2 3 4 5 6)
 
(remove 7 (list (1 2 3 1 4 5 1 6)) 
=> (1 2 3 1 4 5 1 6)



 



b. Write an iterative process version of remove that has the same input/output behavior as your recursive process version. 



 



c. An easy way to define remove is to use the higher-order procedure filter, defined below: 



 
(define (filter pred lst)
   (cond ((null? lst) nil)
         ((pred (car lst)) (cons (car lst)
                                 (filter pred (cdr lst))))
         (else (filter pred (cdr lst)))))
 



Supply the missing expressions in the following skeleton for remove using filter. 



(define (remove elt lst)
   (filter  <exp1>



            <exp2>))



 



6. Higher-order list operator



The following procedure myAccumulate applies a term procedure to each item in a list lst and combines the results by successively applying a combiner procedure, beginning with a given null-value: 



 
(define (myAccumulate combiner null-value term lst)
   (if (null? lst)
       null-value
       (combiner (term INSERT1)
                 (myAccumulate combiner
                             null-value
                             term
                             INSERT2))))
 



a. Complete the procedure myAccumulate by fill in the expression INSERT1 and INSERT2.



 



b. Complete the following call to myAccumulate for computing the sum of the squares of the elements in a given list of numbers, e.g., given the list (1 2 3), we should be 14 (= 1 + 4 + 9). You can assume that the procedure square has already been defined. 



 
(myAccumulate <exp1> 
            <exp2> 
            <exp3> 
            list-of-numbers)
 



c.  
Use instead accumulate and map to computing the sum of the squares of the elements in a given list of numbers.
 
d. What is the type of accumulate and map?



7. Order of Growth



What are the Orders of Growth (space and time) for the two procedures listed below? 



 
(define (fact1 n)
   (define (helper cur k)
       (if (= k 1)
           cur
           (helper (* cur k) (- k 1))))
   (helper 1 n))
 
(define (fib1 n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib1 (- n 1))
                  (fib1 (- n 2))))))
 
(define (fib2 n)
    (define (fib-iter a b count)
       (if (= count 0)
           b
           (fib-iter (+ a b) a (- count 1))))
 (fib-iter 1 0 n))





8. Depth of a Tree



Write a function depth that takes a tree and returns the maximum depth of the tree. Note that this is equivalent to the maximum number of parenthesis open at any given time when scheme prints the tree. For example, 



 
(depth (list 1 (list (list 2) 3) (list 4))) ==> 3 
(define (depth tree) FILL IN HERE )
 



Now write depth using map and accumulate... 



(define (depth tree)  FILL IN HERE )



9. Write map-tree.



Write a procedure, (map-tree op tree) so if tree has value 



 



(((1 2) 3) (4  (5 6)) 7 (8 9 10))



 



then 



 



(map-tree inc tree)



 



has value 



(((2 3) 4) (5 (6 7)) 8 (9 10 11)) 



 



(tip. 



use leaf? and map.)



 



10. Symbols



 



(eq? (cons 'a nil) (cons 'a nil)) 



(equal? (cons 'a nil) (cons 'a nil)) 



(define w (list 'a 'b 'c)) 



(eq? w (cdr (cons 'b w))) 



(eq? (cdr w) (cdr w)) 



 



(define a 3)



(define b 4)



(define c (list 5 6)) 



(define d '(a b))



(define p (list cons +)) 



(define q '(cons +)) 



(define r (list 'cons '+))



 



(list 'a b) ==>



'(a b) ==>



(cons b d) ==>



(list 'b c) ==>



(car d) ==>



((car p) 3 4) ==>



((cadr p) 3 4) ==>



((car r) 3 4) ==>



((cadr q) 3 4) ==>



(car ''a) ==>