You should read through the end of Section 1.3.3 in order to be fully prepared for this lab.
As you answer the problems below, make a note on how long you spent on each of the sections.
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.
Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.
[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.
(define (expt x y)
(if (= y 0)
1
(* x (expt x (- y 1)))))
(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))
(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))))))
(define (exp2 y)
(if (= y 0)
1
(+ (exp2 (- y 1)) (exp2 (- y 1)))))
[10] Write the following lambda expressions:
A lambda expression which takes a number, adds one to that number, and then squares the result.
A lambda expression which takes a function (of one argument) and a number, and applies the function to twice the number.
[30] What's wrong with these expressions?
(define a 3) (define b (lambda (x) (* x 2))) (a b)
(define a 3) (define b (lambda (x) (* x 2))) (b b)
(let (a 3)
(* a 2))
(let ((a 3)
(* a 2)))
(lambda (x) (let ((a 3))) (* a x))
(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.)
[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))
[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.
[30] Exercise 1.31 (higher-order procedures and converting from recursive to iterative functions or vice versa)
[30] Exercise 1.32 (next step abstracting up)
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:
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:
(display <anything>)) prints out the value of
<anything>.(newline) prints a newline character.(begin expr1 expr2 ...) evaluates expr1,
expr2 etc. in order, returning the value of the last
expression.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.)
[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.
[40] For Exercise 1.26:
This problem addresses the theory and model, so there are no additional details here.
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:
Start with a function f of one variable, an x interval from a to b, a threshold for x and a threshold for y (i.e. f(x)). For the method to work, f(a) and f(b) must have opposite signs i.e. one must be greater than zero and one must be less than zero.
If a and b are close enough, stop and return a. The criterion for being close enough is that the distance between a and b must be within the x threshold and the distance between f(a) and zero must be within the y threshold. This is the base case.
Otherwise, find the midpoint between a and b and evaluate the function f at a, b and at the midpoint between a and b. If f(a) and f(midpoint) have the same sign, call the root solver recursively on the interval from the midpoint to b (note that f(b) must have a sign different from f(midpoint) in this case). Otherwise, call the root solver recursively on the interval from a to the midpoint (in this case, f(a) must have a sign different from f(midpoint)).
Note that with every recursive call, the length of the interval diminishes by a factor of 2. Eventually, the interval will become small enough that the base case will apply, and we'll have our answer.
(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))
(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.
[10] Find both roots of the given quadratic equation [x2+0.001x-0.00000011] using one of the implementations.
[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.)
[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.)
[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?
[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.)
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.