CS 22

Clab 6: Slow growth, rapid growth, more with lists

I'll say a few words about logarithms and especially logs to base 2 and and the G-rated version of Ackermann's function.

Since I don't have superscripts and subscripts on these pages, I will use log n to represent log to the base 2 of n and x^y to represent x raised to the y power.
Recall that log n = k if 2^k = n. So log 16 = 4, log 32 = 5,
log 128 = 7, log 1024 = 10.
Keep in mind that:
100^3 = 1,000,000
log 1,000,000 is about 20
2^100 >> the number of microseconds since the big bang.
This means that if your algorithm has a running time of O(2^n) on inputs of size n, and if you want to use it on an input of size 100, you will have to wait a looooong time to get an answer even if your computer performs a million steps a second. O(n^3) algorithms don't take too long on 100 inputs and O(log n) algorithms are fast on 1,000,000 inputs.

Here is the G-rated version of Ackermann's function.

;;EXERCISE 1.10 (define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1)))))) If you define f(x) to be A(x,x), f is a computable function that is extremely rapidly growing. The sun will become a red giant and swallow the earth before our fastest computers can finish computing f(4).

Here is an iterative version of expt that runs in O(log n) time. ;; for x,y,z integers initially >= 1, ;; assuming it starts with x(y^z) = b^n ;; exp-iter maintains this invariant each ;; time it is invoked (define (exp-iter x y z) (cond ((= z 1) (* x y)) ((even? z) (exp-iter x (square y) (/ z 2))) (else (exp-iter (* x y) y (- z 1))) ) ) (define (expt b n) (exp-iter 1 b n)) (define (square x) (* x x ))

Here is one of the list functions from last clab.

;; remove-all returns a list with all occurrences of sym ;; removed from list l: (define remove-all (lambda (sym l) (cond ((null? l) '()) ((equal? (car l) sym) (remove-all sym (cdr l))) (else (cons (car l) (remove-all sym (cdr l)))))))

Now, define and debug the following functions.
Ask questions if you have them.
Make sure your language level is Full Scheme.
;; subst returns a list with all occurrences of old ;; replaced with new in list l: (define subst (lambda (new old l) .... ;; count returns the number of times the atom sym occurs in the ;; list l: (define count (lambda (sym l) ..... ;; rev returns the reverse of the list lst (define rev (lambda (lst) ... For example: > olymp (skating skiing slalom bobsled) > (rev olymp) (bobsled slalom skiing skating)

Start on Homework 6 (due M, Feb. 4) and ask any questions you may have.