CS 37

Clab 6: Slow growth, rapid growth, Divide and Conquer; Functions as first-class objects, 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).

Review the material in text on pp. 62-65 on lambda and let http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.2 . From r5rs in on-line help in drscheme, read about lambda and let (the binding construct meaning -- shun the sinful iteration material) Make sure you understand the examples illustrated and how the values were obtained. Ask questions if you have them.

Now enter the search procedure given on page 67.

(define (search f neg-point pos-point) (let ((midpoint (average neg-point pos-point))) (if (close-enough? neg-point pos-point) midpoint (let ((test-value (f midpoint))) (cond ((positive? test-value) (search f neg-point midpoint)) ((negative? test-value) (search f midpoint pos-point)) (else midpoint)))))) (define (close-enough? x y) (< (abs (- x y)) 0.001)) (define average (lambda (x y) (/ (+ x y) 2))) (define cube (lambda (x) (* x x x))) Make sure you understand what it is doing. You will need to define average and close-enough? if you have not done so already. The function cube that we have used before has a root at 0. Test search by evaluating: (search cube -1 2.0). This is an example of a divide and conquer algorithm. Divide and conquer is a general algorithm design technique. Using this technique, one tries to find a way to divide a problem in half (approximately) and then solve just half a problem (or even two halves sometimes, hoping that solving two halves will be easier than solving one whole). Turn trace on search and average and evaluate (search cube -1 2.0) again. Make sure you see how the algorithm is dividing the region where the root may be in half each pass through. The number of thousandths (.001s) between -1 and 2 is 3000 so you can se that the complexity of this algorithm is logarithmic in the size of the interval divided by the accuracy desired.

x^2-4 is a function with root at 2. Without naming this function, we can express it as (lambda (x) (- (square x) 4)). Try search on this function by evaluating: (search (lambda (x) (- (square x) 4)) 0 3.0). Check that you got the root.

1-x is the equation of the straight line that passes through the the points (0, 1) and (3, -2). We can express it as (lambda (x) (- 1 x)). Find the root of 1 -x by evaluating: (search (lambda (x) (- 1 x)) 0 3.0). You should have gotten an answer. BUT--Don't bet your life on the answer you got. What is the right answer? Did you get the right answer? Why not? What do you have to do to get the right answer? Now read page 67 again and then page 68.

Now carefully review the material on pages 73-75. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.4

Define deriv as in the text . Note that deriv is a procedure that takes one argument, a function, and returns a function that is an approximation to the derivative of the first argument. deriv expects to be executed in an environment where dx is defined to be a small positive real number (e.g. 0.00001). You should have the functions square and cube defined from before. If not, define them now. Define dx to be 0.001. Now evaluate

(define Dsquare (deriv square)) Dsquare is a function that is an approximation to the derivative of x^2. That is Dsquare is a function that should be very close to the function 2x. Try evaluating Dsquare on some values and check that it does behave like an approximation to the function 2x. Now evaluate (define g (deriv cube)) g should be an approximation to the function 3x^2 which is the derivative of x^3. Check it on a few values.

The composition of 2 functions f and g, sometimes written fg is defined by fg(x) = f(g(x)). That is first apply g to x, then apply f to the result. For example if f(x) = x^3 and g(x) = 1 + x, then fg(x) = (1 + x)^3. We want to define a procedure that takes two functions as arguments and returns the composition of those two argument functions. Here is a start:

;;;given the 2 functions f and g, compose returns the composition fg (define (compose f g) (...you fill in this part) ;;; for convenience we will define the function 1+ which increments ;;; its argument by one. (define 1+ (lambda (x) (+ 1 x))) For example: > (1+ 7) 8 After you have successfully defined compose, you should be able to evaluate: (define h (compose cube 1+)) If you did it right h should be the function h(x) = (1 + x)^3.

Try it and check h for a few values. Try some other compositions.

Ask any questions you may have.

Now, define and debug the following functions.
Ask questions if you have them.
Make sure your language level is Full Scheme.

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