CS 1 Fall 2007

Lab 3: Called to a Higher Order

Assigned: Monday, October 15, 2007
Due: Thursday, October 25, 2007, 02:00:00


You should read through the end of Section 1.3.3 in order to be fully prepared for this lab.

Part @: Time Synopsis

  1. As you answer the problems below, make a note on how long you spent on each of the sections.

  2. If any of the individual problems took you notably more time than the rating stated, please identify them and write down your actual time spent. This will help us calibrate future problem sets.


Part A: Exercises

Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.

  1. [40] What is the order of growth in time, or (worst-case) time complexity, for each of the following procedures?

    Be sure to express your answers in terms of the procedures' input variables.

    1.   (define (expt x y)
          (if (= y 0) 
              1
              (* x (expt x (- y 1)))))
      
    2.   (define (expt x y)
          (define (expt-aux x y p)
            (if (= y 0) 
                p
                (expt-aux x (- y 1) (* x p))))
          (expt-aux x y 1))
      
    3.   (define (expt x y)
          (define (square x) (* x x))
          (if (= y 0) 
              1
              (if (even? y)  ; even? is a primitive procedure in Scheme
                  (square (expt x (/ y 2)))
                  (* x (expt x (- y 1))))))
      
    4.   (define (exp2 y)
           (if (= y 0) 
               1
               (+ (exp2 (- y 1)) (exp2 (- y 1)))))
      
  2. [10] Write the following lambda expressions:

    1. A lambda expression which takes a number, adds one to that number, and then squares the result.

    2. A lambda expression which takes a function (of one argument) and a number, and applies the function to twice the number.

  3. [30] What's wrong with these expressions?

    1.   (define a 3)
        (define b (lambda (x) (* x 2)))
        (a b)
      
    2.   (define a 3)
        (define b (lambda (x) (* x 2)))
        (b b)
      
    3.   (let (a 3)
             (* a 2))
      
    4.   (let ((a 3)
              (* a 2)))
      
    5.   (lambda (x) (let ((a 3))) (* a x))
      
    6.   (define (x) (* x 3))
        (x)
      

    After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs". (You do not need to include the results in your write-up.)


Part B: Book Exercises

Please work the following exercises from the textbook:
  1. [30] Exercise 1.17 (multiplication in log steps)

    You should include these definitions for double and halve in your code:

      (define (double x) (* x 2))
      (define (halve x) (/ x 2))
    
  2. [60] Exercise 1.29 (Simpson's rule, taking a function as an argument)

    NOTE: There are many ways to do this problem, ranging from the straightforward to the very obscure. You are free to use any method you like (as long as it works!) but see here if you want a hint. Also, we suggest that you use real numbers to write coefficients in your expansion (i.e. 1.0 instead of 1). Otherwise, Scheme will use rational arithmetic in its computations.

  3. [30] Exercise 1.31 (higher-order procedures and converting from recursive to iterative functions or vice versa)

  4. [30] Exercise 1.32 (next step abstracting up)


Part C: Order of Growth Implications

SICP has a series of exercises involving tests for primality. With the following suggestions and additions, complete exercises 1.22, 1.24, and 1.26:

  1. [45] For Exercise 1.22:

    This exercise uses the prime? procedure defined in the beginning of section 1.2.6. You'll need to copy that code (either by hand from the book, or by copy-and-pasting from the web) into your Scheme file first. The procedures you'll need include smallest-divisor, find-divisor, divides?, and prime? itself. Since find-divisor also depends upon square, you'll have to spend a moment providing a square implementation as well.

    This exercise also uses some Scheme procedures introduced in day 7's lecture:

    Also, this exercise depends on a built-in Scheme procedure named runtime to obtain timing data. DrScheme has this procedure, but it has a different name: current-milliseconds. You'll need to key in the provided code for timed-prime-test, start-prime-test, and report-prime, but add the following definition for runtime -- all it does is map the runtime name to the built-in current-milliseconds procedure.

      (define (runtime) (current-milliseconds))
      

    To make the display less cluttered, change the Scheme procedures from the book used for displaying the results to these:

      (define (timed-prime-test n)
        (start-prime-test n (runtime)))
    
      (define (start-prime-test n start-time)
        (if (prime? n)
            (begin
              (display n)
              (report-prime (- (runtime) start-time)))))
    
      (define (report-prime elapsed-time)
        (display " *** ")
        (display elapsed-time)
        (newline)) 
      

    Finally, computing speeds have improved since this problem was written. If you attempt to make time measurements for primes around 103, 104, 105, or 106, you'll find that the lab machines are able to find these primes in times that are too quick for the resolution of the current-milliseconds procedure! Instead, start by finding the five large primes smaller than 109 and then go up to 1010, 1011, and 1012. For instance, evaluate:

      (search-for-primes 999999700    1000000000)
      (search-for-primes 9999999700   10000000000)
      (search-for-primes 99999999700  100000000000)
      (search-for-primes 999999999700 1000000000000)
      

    Instead of reporting primes for the ranges given in the book problem, show the five largest primes found in each of these searches, and show the average time taken to compute the five primes for each search. Does this average time increase by a factor of sqrt(n) as n increases by a factor of 10 for all of these searches? If not, can you think of a reason why not? (If you're stuck on this last point, ask your TA for a hint, as it involves ideas not covered in class.)

  2. [20] For Exercise 1.24:

    fast-prime? uses random, a random-number-generating primitive in Scheme, to create test values for its probabalistic prime analysis. Unfortunately, due to underlying computer architecture issues, random will only generate random numbers between 0 and 2147483647. Since you'll want to test fast-prime? against the same, larger order-of-magnitude numbers as you did for part A, you'll need to replace the call to random in the fermat-test function with a call to this new function, big-random:

    (define (big-random n)
      (if (<= n 2147483647)
          (random n)
          (* (random 2147483647) (big-random (round (/ n 2147483647))))))
      

    Also, don't use false for the boolean false value in the fast-prime? function; use #f instead. false will work in DrScheme, but it isn't standard Scheme, so you shouldn't use it.

    Use the same prime number ranges from above for testing fast-prime?'s real-world time complexity. Do 1000 tests for each call to fast-prime?. Note that you don't have to write any code for this problem; you just have to modify start-prime-test to use fast-prime? instead of prime?. Are the results consistent with a log(n) complexity for the fast-prime? procedure? Note that a procedure with a log(n) complexity will have a time requirement which increases by a constant factor when the size of the input is multiplied by 10.

  3. [40] For Exercise 1.26:

    This problem addresses the theory and model, so there are no additional details here.


Part D: Good Code, Bad Code

A root solver finds solutions to the equation f(x) = 0 for some function f. Included here are two different implementatons of an extension of the basic half-interval root solver developed in section 1.3.3 of the text. One attempts to use abstraction well, while the other attempts to use minimal abstraction.

For some functions, the half-interval root solver may determine an approximation x which is very close to a root x*, but f(x) may not be very close to zero (because the slope mqy be very steep at the root). You could keep defining new solvers with tighter thresholds for x until you can find a root which brings f(x) sufficiently close to zero. Alternately, you could require that both the x interval be below some threshold and the function value f(x) be below some threshold before terminating the search. The implementations below provide this additional requirement on the solutions they find.

The algorithm we'll use can be described informally as follows:


An Abstracted Solution

  (define (half-interval-solve fun xthreshold ythreshold
                               interval-low interval-high)
     (define (close-enough? a b)
        (and (< (abs (- a b)) xthreshold) 
             (< (abs (fun a)) ythreshold))) 
     (define (same-sign? a b)
        (or (and (< a 0) (< b 0))
            (and (> a 0) (> b 0))))
     (define (midpoint a b)
        (/ (+ a b) 2.0))
     (define (half-interval-solve-aux interval-low interval-high)
       (if (close-enough? interval-low interval-high) 
           interval-low
           (let ((interval-mid (midpoint interval-low interval-high)))
             (let ((value-low (fun interval-low))
                   (value-mid (fun interval-mid))
                   (value-high (fun interval-high)))
               (if (same-sign? value-low value-mid)
                   (half-interval-solve-aux interval-mid interval-high)
                   (half-interval-solve-aux interval-low interval-mid))))))

     (if (same-sign? (fun interval-low)
                     (fun interval-high))
         (error "Starting interval points should be of opposite sign")
         (half-interval-solve-aux interval-low interval-high)) )

(define quadratic-equation 
  (let ((a 1.0)          ;; coefficients for quadratic equation
        (b 0.001) 
        (c -0.00000011)) 
    (lambda (x) (+ (* a x x)  (* b x) c))))

(define (solve-quadratic-equation interval-low interval-high)
  (half-interval-solve
   quadratic-equation
   0.001 ;; xthreshold
   0.001 ;; ythreshold
   interval-low
   interval-high))

A Minimally-Abstracted Solution

  (define (solve-quadratic-equation a b)
    (if (and (< (abs (+ (* a a) (* 0.001 a) -0.00000011)) 0.001)
             (< (abs (- a b)) 0.001))
        a
        (if (or (and (< (+ (* a a) (* 0.001 a) -0.00000011) 0)
                     (< (+ (* (/ (+ a b) 2.0) (/ (+ a b) 2.0)) 
                           (* 0.001 (/ (+ a b) 2.0)) -0.00000011) 
                        0))
                (and (> (+ (* a a) (* 0.001 a) -0.00000011) 0)
                     (> (+ (* (/ (+ a b) 2.0) (/ (+ a b) 2.0)) 
                           (* 0.001 (/ (+ a b) 2.0)) -0.00000011) 
                        0)))
            (solve-quadratic-equation (/ (+ a b) 2.0) b)
            (solve-quadratic-equation a (/ (+ a b) 2.0)))))


Many of the questions which follow ask you to provide the same, new, or different functionality for both implementations. When asked to provide code, in each case, you should answer the question in the style of the respective base implementation.

  1. [10] Find both roots of the given quadratic equation [x2+0.001x-0.00000011] using one of the implementations.

  2. [30] For both implementations, change the equation being solved to [sin(2x)-2cos(x)] and find the roots of this equation for x between 0 and 2*pi, where pi = 3.1415926.... (Just turn in the new function definitions.)

  3. [20] Increase the x-threshold precision to 0.0000001 while relaxing the y-threshold to 1.0 for both implementations and both equations mentioned in previous parts of this problem.
    (Again, turn in the new function definitions.)

  4. [10] Assuming we had ask you to solve a large number (say more than 10) of equations and to experiment with several x and y threshold values, which style would require you to write more total code? Why?

  5. [15] What makes the "Abstracted" code good and the "Minimal Abstraction" code bad?
    (Identify the stylistic differences between these two implementations and comment on the reasons the "Abstracted" style might be preferable to the "Minimal Abstraction" style.)


Hint for problem B.2 (1.29 in SICP)

One way to deal with the Simpson's rule coefficients is to define a procedure called simpsons-coeff that computes the correct coefficient of the Simpson's rule expansion based on the index of the term (0, 1, 2, ... n). The procedure will have a skeleton that looks something like this:

(define (simpsons-coeff i n)
  (cond ((= i 0)  <??>) ; fill in your code for <??>
        ((= i n)  <??>)
        etc.))

Then you can use a simple iterative procedure to calculate the sum of the Simpson's rule expansion. There are cleverer ways to solve this problem, but they aren't really much better.