6.001 Quiz Review – March 5, 2003

1. Warm-up

(define (three) 3) undef

three proc ->number

(three) 3 number

(define four 4) undef

four 4 number

(four) error

(+ (three) four) 7 number

(define (add-x x) undef

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

add-x proc number->(number->number)

(add-x 10) proc number->number

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

(add-10 5) 15 number

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

(apply-to-3-and-4 +)
(apply-to-3-and-4 (lambda (x y) (+ x y)))
 

b. 1

 
(apply-to-3-and-4 (lambda (x y) (- y x)))

c. 2

 
(apply-to-3-and-4 (lambda (x y) (/ y 2)))
(apply-to-3-and-4 (lambda (x y) ( - (* x 2) y)))
 

d. 3

 
(apply-to-3-and-4 (lambda (x y) x))
 

e. 4

 
(apply-to-3-and-4 (lambda (x y) y))
 

3. Recursive procedures

 
a.
 

(define (add a b)

(if (= a 0)

b

(inc (add (dec a) b))))

b. 

(define (subtract a b)

(if (= b 0)

a

(subtract (dec a) (dec b))))

(define (subi a b)

(define (help sum b)

(if (= b 0)

sum

(help (- sum 1) (- b 1))))

(help a b))

4. High-order procedure

 
a. 
(define (create-apply-to-x-and-y x y)
(lambda (p) (p x y)))
 

b.

(define (sum term a next b)

(if (> a b)

 0

(+ (term a)

  (sum term (next a) next b))))
 
c.
(sum square 1 (lambda(x) (+ x 1)) 10)
 

5. High-order list procedure

a.

 
(define (remove elm lst) 
 (if (null? lst)
 nil
 (if (= elm (car lst))
  (remove elm (cdr lst))
  (cons (car lst) (remove elm (cdr lst)))))) 
 

b.

(define (remove elm lst)

(define (remove-iter new-lst old-lst)

(if (null? old-lst)

new-lst

(if (= elm (car old-lst))

(remove-iter new-lst (cdr old-lst))

(remove-iter (cons (car old-lst) new-lst)

(cdr old-lst)))))

(remove-iter '() lst))

c.

(define (remove elm lst)
(filter (lambda (x) (not (= x elm))) lst))

6. High-order list operator

(define (accumulate op init lst)

(if (null? lst)

init

(op (car lst)

(accumulate op init
(cdr lst)))))

(accumulate + 0 (map inc (filter odd? w)))

(2 + 4 + 6) à 12

 
a.

INSERT1: (car lst)

INSERT2: (cdr lst)

(define (myAccumulate combiner null-value term lst)

(if (null? lst)

null-value

(combiner (term (car lst))

(myAccumulate combiner

null-value

term

(cdr lst)))))

 
 
b.
(myAccumulate + 0 square list-of-numbers)

c.

(accumulate + 0 (map square list-of-numbers))

d.

Acc (AàB, B, List<A>) à B

Map (AàB, List<A>) à List<B>

MyAcc (BàB, A, AàB, List<A>) à B

7. Order of Growth

(define (fact1 n)
 (define (helper cur k)
 (if (= k 1)
 cur
 (helper (* cur k) (- k 1))))
 (helper 1 n))
 

Time = n, Space = n

 
(define (fib1 n)
 (cond ((= n 0) 0)
 ((= n 1) 1)
 (else (+ (fib1 (- n 1))
 (fib1 (- n 2))))))

Time = 2^n, Space = n

 
(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))

Time = n, Space = 1

8. Depth of a Tree

(define (depth tree)

(if (not (pair? tree))

0

(max (+ 1 (depth (car tree))) (depth (cdr tree)))))

(define (depth tree)

(if (not (pair? tree))

0

(+ 1 (accumulate max 0 (map depth tree)))) )

9. More trees

(define map-tree

(lambda (op tree)

(if (leaf? tree)

(op tree)

(map (lambda (subtree) (map-tree op subtree))

tree))))

10. Symbols

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

#f

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

#t

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

"w --> (a b c)"

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

#t

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

#t

(list 'a b)

;Value: (a 4)

'(a b)

;Value: (a b)

(cons b d)

;Value: (4 a b)

(list 'b c)

;Value: (b (5 6))

(car d)

;Value: a

((car p) 3 4)

;Value: (3 . 4)

((cadr p) 3 4)

;Value: 7

((car r) 3 4)

;The object cons is not applicable.

((cadr q) 3 4)

;The object + is not applicable.

(car ''a)

;Value: quote