You should read through the end of Section 1.3.3 of SICP in order to be fully prepared for this lab.
If you choose to use internal procedures in any of the procedures you use in this lab, you need to know that the way this was described in lecture 5 is not supported in the DrScheme Intermediate Student with Lambda language level (or in any of the student language levels, for that matter). However, an equivalent variant of internal procedures is supported, which you can use instead.
Here is how you define an internal procedure in standard Scheme:
(define (factorial n)
(define (iter n r)
(if (= n 0)
r
(iter (- n 1) (* n r))))
(iter n 1))
And here's how you would write the exact same function in DrScheme's Intermediate Student with Lambda language level:
(define (factorial n)
(local ((define (iter n r)
(if (= n 0)
r
(iter (- n 1) (* n r)))))
(iter n 1)))
As you can see the main difference is that all the internal
defines have to be inside this new local special form,
and more specifically they have to be part of the first operand to
local, which is a parenthesized list of all the internal
defines. We realize that it's annoying to have to learn two
completely different ways to do the exact same thing, but this is a reflection
of the fact that (a) Scheme has many different dialects, and (b) the two
textbooks we are using (SICP and HtDP) use different ones. Sorry for the
inconvenience. Note that DrScheme can handle standard Scheme as well if you use
either the "R5RS" language level or the "Pretty Big Scheme" language level.
However, those language levels don't provide the "check-expect" function for
testing. The "module" language level (which is the most advanced level of all)
can do everything, but using it is a bit more complicated. We'll get to that in
a lab or two, after which we will forget about language levels.
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? For each problem, give a one or two sentence explanation for why the procedure has the time complexity it has. Make sure you pay particular attention to which argument to the procedure controls the termination of a procedure call, and how quickly this argument changes in a recursive call (i.e. does it go down by one? or divide by two?).
Be sure to express your answers in terms of the procedures' argument names.
(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)))))
[40] For this exercise, you'll be defining some simple functions and reasoning about their time complexity. Let's say that in a book you see the following recursive definition for how to compute 2N for some number N:
20 = 1 2N = 2N-1 + 2N-1
Convert this definition into an exactly equivalent tree-recursive
function called two-to-the-power-of. Describe its asymptotic time
complexity and explain why it has this time complexity.
Now write a function called tttpo_rec which computes
the exact same thing, but which uses a linear recursive process which has an
O(n) time complexity and also uses O(n) space for its pending operations.
Now write a function called tttpo_iter which computes
the exact same thing, but which uses a linear iterative process which has an
O(n) time complexity and also uses constant space.
Now let's say you want to generalize one of the preceding
definitions so that it will handle arbitrary integer powers, so that you can
compute 2N, 3N etc. Write a function called
to-the-power-of that takes two arguments and raises one to the
power of the other. Here's the template:
;; to-the-power-of: integer integer -> integer ;; This function raises m to the power of n, returning the result. ;; m must be > 0 and n >= 0. (define (to-the-power-of m n) ...) (check-expect (to-the-power-of 1 0) 1) ; base case (check-expect (to-the-power-of 2 3) 8) ; recursive case (check-expect (to-the-power-of 3 2) 9) ; recursive case
We'll add one more restriction: you can't use the * operator;
you can only use the following recursive function to do multiplications:
;;; multiply: integer integer -> integer ;; This function multiplies two non-negative integers, returning the result. ;; Its time complexity is O(a). (define (multiply a b) ...) ;; done in lab 2
Write the function, and describe what its time complexity is and why.
[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))
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.)
Please work the following exercises from the textbook (SICP). Make sure that your procedures have correct contracts, comments, and tests.
[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 here's a hint:
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 template that looks something like
this:
;; simpsons-coeff: integer integer -> integer
;; This function returns the Simpson's rule coefficients for an index i and
;; a maximum index n.
(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.
[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)
With apologies to Monty Python, there is no part C this week.
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 may 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 length of 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.
;; half-interval-solve: (number -> number) number number number number -> number
;; This function finds a root of the function 'fun' in the given range.
(define (half-interval-solve fun xthreshold ythreshold
interval-low interval-high)
;; We use standard Scheme internal procedures here.
(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. Use the "Pretty Big" language level of DrScheme for all of the questions in this section. (This is just standard Scheme as described in SICP, along with a few other useful features.)
[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.)