6.001 Recitation #5 – Feb 19, 2003

 

RI: Konrad Tollmar

www.ai.mit.edu/6001

 

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

 

  1. doublefun
  2. (car doublefun)
  3. (cdr doublefun)
  4. (car (car doublefun))
  5. (car (cdr doublefun))
  6. Use doublefun to create a list that has the following printer representation: ;Value: (6 0 0 1)

 

2. Common list operations

 

x => (())

y => (1 2 3)

z => (1 (2 3) ((4)))

w => (1 2 3 4 5)

 

 

  1. (length x)
  2. (length y)
  3. (length z)
  4. (list-ref z 2)
  5. (append x y)
  6. (cons x y)

3. Write a procedure copy-some

Write the procedure copy-some that copies the first n elements of a list, i.e.

(copy-some 3 (list 1 2 3 4 5)) ==> (1 2 3) 

 

 

4. What is the type?

 

  1. 6001
  2. "is fun"

 

  1. #t
  2. (> 5 4)

 

 

 

  1. >                         

 

  1. (define (inc x) (+ x 1))
  2. (lambda (x) (+ x 1))
  3. (lambda (x) x))

 

 

 

 

5. What are the types of these procedures?

     1. length          

     2. list-ref        

     3. append

6. Find function f

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

 

 

R(n)=6

R(n)=n2 + 3

R(n)=6*n3 + 3*n2 + 7n + 100

R(n)=23n+7

 

 

7. Estimate the order of growth.

What is simplest expression for the order of growth of running time
of procedure copy-some, last-k, mul1 & mul2? What about space?

 

(define (last-k k lst)

 (if (= (length lst) k) lst (last-k k (cdr lst))))

 

 

(define (mul1  n m)
 (if (= n 0) 0 (+ m (mul1 (- n 1) m))))

 

 

(define (mul2 n m)
      (define (help count ans)
        (if (= count 0)
            ans
            (help (- count 1) (+ m ans))))
      (help n 0))

 

 

1. Q(1), 2. Q(log n), 3. Q(n), 4. Q(2^n)

 

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

 

Write a procedure mul3 that computes m*n in Q(log n) time. Write similar procedure mul4 that does the same job and in Q(1) space.

 

Hint: n*m = 2 * ( (n / 2) * m) if n even, n*m = m + ((n-1) * m) if n odd.

 

9. Data abstractions

 

You and your partner have been asked to build a small vector package. Firstly should you together define an interface to this package, i.e. the constructor, selectors and operations. Secondly, one of you implements the constructors and the selectors, while your partner implement a couple of vector operations. Last verify that your code work together and prepare a brief presentation.