6.001 Recitation #5 – Feb 19, 2003

RI: Konrad Tollmar

www.ai.mit.edu/6001

• Pairs and lists

• Common list operations

• Types

• Order of growth

• Data abstractions

1. Revisit - Pairs and lists

(define doublefun

(list (cons (+ 2 4) nil) (cons 0 (cons 0 (cons 1 nil)))))

doublefun

;Value: ((6) (0 0 1))

(car doublefun)

;Value: (6)

(cdr doublefun)

;Value: ((0 0 1))

(car (car doublefun))

;Value: 6

(car (cdr doublefun))

;Value: (0 0 1)

(cons (car (car doublefun)) (car (cdr doublefun)))

;Value: (6 0 0 1)

2. Common list operations

(length x) -> 1

(length y) -> 3

(length z) -> 3

(list-ref z 2) -> ((4))

(append x y) -> (() 1 2 3)

(cons x y) -> ( (()) 1 2 3)

3. Write a procedure copy-some

(define (copy-some n lst)

(if (= n 0) nil (cons (car lst)(copy-some (- n 1) (cdr lst))))

4. What is the type?

Every expression has a value, every value has a type.

Primitive types:

A/ 6001

Number

B/ "is fun"

String

C/ #t

Boolean

D/ (> 5 4)

Boolean

Special form:

E/

(define (inc x) (+ x 1))

Undef

F/

>

Proc

G/ (lambda (x) (+ x 1))

Proc: Num -> Num

H/ (lambda (x) x)

Proc: A -> A(identity function – why?)

5. What are the types of these procedures?

1. length

List<A> -> Num

2.

list-ref

List<A>,Num -> A

3. append

List<A>, List<A> -> List<A>

6. Find function f

For each, find simplest and slowest growing f for which R(n)=Q(f(n))

•R(n)=6

Q(1) 1 * 1 <= 6 <= 6 * 1 for all n

•R(n)=n² + 3

Q(n²) 1*n² <= n² + 3 <= 2*n² for all n > 2

•R(n)=6*n³ + 3*n² + 7n + 100

Q(n³) 1*n³ <= 6*n³ + 3*n² + 7n + 100 <= 7*n³ for all n>100

•R(n)=2³ⁿ⁺⁷

Q(8ⁿ) 1*8ⁿ <= 2³ⁿ⁺⁷ <= 2⁸*8ⁿ for all n>0

7. Reduce a calculation from Q(n) to Q(log n)

(define (mul3 n m)

(cond ((= n 0) 0)

((even? n) (double (mul3 (half n) m)))

(else (+ m (mul3 (- n 1) m)))))

(define (mul4 m n)

(define (mul4-iter m count ans)

(cond ((= count 0) ans)

((even? count)

(mul4-iter (double m) (half count) ans))

(else

(mul4-iter m (- count 1) (+ m ans)))))

(mul4-iter m n 0)

)