HW 3: Due 20 October, 2004 at 5PM

1.) Design a procedure that evolves an iterative exponentiation process 
that uses successive squaring and uses a logarithmic number of steps, as 
does ^-logrecursive. 
(Hint: Using the observation that (b^(n/2))^2 = (b^2)^(n/2), keep, 
along with the exponent n and the base b, an additional state variable a, 
and define the state transformation in such a way that the product a b^n 
is unchanged from state to state. At the beginning of the process a is taken 
to be 1, and the answer is given by the value of a at the end of the 
process. In general, the technique of defining an invariant quantity that 
remains unchanged from state to state is a powerful way to think about the 
design of iterative algorithms.)

2.) There is a clever algorithm for computing the Fibonacci numbers in a 
logarithmic number of steps. Recall the transformation of the state 
variables a and b in the fib-iterative function: cur <-- cur + prev and 
prev <-- cur a. Call this transformation T, and observe that applying T 
over and over again n times, starting with 1 and 0, produces the pair  
Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced 
by applying T^n, the nth power of the transformation T, starting with the 
pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a 
family of transformations Tpq, where Tpq transforms the pair (a,b) 
according to a <-- bq + aq + ap and b <-- bp + aq. Show that if we apply 
such a transformation Tpq twice, the effect is the same as using a single 
transformation Tp'q' of the same form, and compute p' and q' in terms of p 
and q. This gives us an explicit way to square these transformations, and 
thus we can compute Tn using successive squaring, as in the fast-expt 
procedure. Put this all together to complete the following procedure, 
which runs in a logarithmic number of steps:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; compute p'
                   <??>      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

3.) Give an implementation of the function "append" that takes
two lists a and b and produces the list whose elements are all of the 
elements of a followed by all of the elements of b.  To avoid confusing 
Dr. Scheme, name your function "myappend".

4.) Give an implementation of the function "reverse" that takes
a list a and produces the list whose elements are the elements of a in 
reverse order.  To avoid confusing Dr. Scheme, name your function 
"myreverse".

5.) Write a function "count-nodes" that takes a binary tree and produces 
the number of nodes it contains.