Ex 1.1.
10, 12, 8, 3, 6, a = 3, b = 3, 19, false, 5, 16, 6, 16

Ex 1.2.

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 3))))) (* 3 (- 6 2) (- 2 7)))

Ex 1.3.

(define (min x y) (if (< x y) x y))

(define (min3 x y z) (min x (min y z)))

(define (square x) (* x x))

(define (sum_of_square x y)
(+ (square x) (square y)))

(define (sum_of_max_two_sqaure x y z)
(define min_num (min3 x y z))
(cond ((= min_num x) (sum_of_square y z))
((= min_num y) (sum_of_square x z))
(else sum_of_square x y)))

(sum_of_max_two_sqaure 1 2 3)

Ex 1.4.
If b is bigger than zero then result is sum of a and b other ways the result is subtraction of a and b.

Ex 1.5.
Honestly, I have not solved the problem at the first place. I can not understand the definition of (p). Then I searched from Internet and get the answer. But I did understand.

(define (p) (p)) will define dead recursion that will execute forever.

If the program run into the dead recursion then the interpreter is using the applicative-order evaluation.

(test 0 (p))
(test 0 ((p)))
(test 0 (((0))))
.... continue recursion

If the program returns 0 then the interpreter is using the normal-order evaluation.

(test 0 (p))
(if (= 0 0) 0 y)
if (true) 0 y)
0

Ex 1.6.
Because of the Applicative evaluation order the new-if will always evaluate the both condition value. In this case the sqrt will enter an infinite recursion.

Ex 1.7.
Because of the the limited precision, 0.001, the procedure is not effective to small numbers.

Following is my solution:

(define (good-enough? next-guess current-guess x)
(or (= (deff (square next-guess) x) 0)
(<
(/
(deff (deff (square next-guess) x)
(deff (square current-guess) x))
(deff (square next-guess) x))
0.001)))

(define (deff a b)
(abs (- a b)))

(define (sqrt-inter guess x)
(if (good-enough? (improve guess x) guess x)
(improve guess x)
(sqrt-inter (improve guess x) x)))

(define (improve guess x)
(average guess (/ x guess)))

(define (average x y)
(/ (+ x y) 2))

Ex 1.8.

(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (good-enough? next-guess current-guess x)
(or (= (deff (cube current-guess) x) 0)
(<
(/
(deff (deff (cube next-guess) x)
(deff (cube current-guess) x))
(deff (cube next-guess) x))
0.001)))

(define (deff a b)
(abs (- a b)))

(define (cube x)
(expt x 3))

(define (cbrt-inter guess x)
(if (good-enough? (improve guess x) guess x)
(improve guess x)
(cbrt-inter (improve guess x) x)))

(define (cube-root x)
(cbrt-inter 1.0 x))

Ex 1.9.

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

recursive;

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

iterative;

1.10.

(A 1 10)
2^10
(A 2 4)
2^16
(A 3 3)
2^16

f(n) = 2n
g(n) = 2^n
h(n) = 2^2^2^...^2, n - 1 times square

1.11.

(define (f_recursive n)
  (if (< n 3)
      n
      (+ (f_recursive (- n 1)) (* 2 (f_recursive (- n 2))) (* 3 (f_recursive (- n 3))))))


(define (f_iterative n)
  (if ( < n 3)
      n
      (iter 0 1 2 (- n 2))))

(define (iter a b c count)
  (if (= count 0)
      c
      (iter  b c (+ c (* 2 b) (* 3 a)) (- count 1))))

1.12.

(define (pascal row col)
  (if (< row col)
      (display 'error)
      (p row col)))

(define (p row col)
  (if (or (= col 1)(= row col))
      1
      (+ (p (- row 1) (- col 1)) (p (- row 1) col))))

Ex 1.13.
It is too hard for me, pure math

Ex 1.14.
IMG_3DB372F9EDB3-1
The required space is n, the longest branch in the tree.
Could not find out the number of steps yet.

Ex 1.15.

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.15))))
(p (p (p (p (sine 0.05)))))
...
  • a. Applied 5 times procedure p when (sine 12.15) is evaluated
  • b. Both growth of space and number of steps are n, since it is a liner recursive.

Ex 1.16.

(define (square n) (* n n))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))

(define (expt b n) (fast-expt-iter b n 1))

Ex 1.17.

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (double (* a (halve b))))
        (else (+ a (* a (- b 1))))))

(define (double n) (+ n n))

(define (halve n) (/ n 2))

Ex 1.18.

(define (multiply-iter a b c)
  (cond ((= b 0) c)
        ((even? b) (multiply-iter (double a) (halve b) c))
        (else (multiply-iter a (- b 1) (+ c a)))))

(define (* a b) (multiply-iter a b 0))

(define (double n) (+ n n))

(define (halve n) (/ n 2))

Ex 1.19.
IMG_0006

(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
                   (+ (* p p) (* q q))
                   (+ (* 2 (* p q)) (* q q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Not finished yet ...