SICP programming exercises

Solved exercises in Scheme (Lisp) from 'Structure and Interpretation of Computer Programs' (MIT Press)

Project maintained by attilagk Hosted on GitHub Pages — Theme by mattgraham

Exercise 1.9

Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

;; procedure A
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
;; procedure B
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

The first + procedure (A) is recursive with deferred operation inc, whereas the second + procedure (B) is iterative with state variables a and b.

The evolution of processes generated when evaluating (+ 4 5) using both + procedures:

;; using the first + procedure (A)
(+ 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
;;
;; using the second + procedure (B)
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

Exercise 1.10 (TODO)

The following procedure computes a mathematical function called Ackermann’s function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of $n$ . For example, (k n) computes $5n^2$ .

Exercise 1.11

A function $f$ is defined by the rule that $f(n) = n$ if $n<3$ and $f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)$ if $n> 3$ . Write a procedure that computes $f$ by means of a recursive process. Write a procedure that computes $f$ by means of an iterative process.

Recursive process:

(define (f n)
  (if (< n 3)
    n
    (+
      (f (- n 1))
      (f (- n 2))
      (f (- n 3)))))

Iterative process:

(define (f-it n)
  (define (f-iter cnt f2 f1 f0)
    (if (= cnt n)
      f2
      (f-iter (+ cnt 1) (+ f2 f1 f0) f2 f1)))
  (if (< n 3)
    n
    (f-iter 3 3 2 1)))

Exercise 1.12

The following pattern of numbers is called Pascal’s triangle.

$\begin{array}{ccccccccc} & & & & 1 & & & & \\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \\ & & & &...& & & & \\ \end{array}$

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.35 Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.

The procedure implements the binomial formula $\binom{n}{k}$ , which corresponds to the $n$ th row in Pascal’s triangle and the $k$ th horizontal position from either side of the triangle in that row.

(define (pascal-tri n k)
  (cond ((or (= 1 k) (= n k)) ;; first base case
         1)
        ((or (> 1 k) (< n k)) ;; second base case
         0)
        (else (+
                (pascal-tri (- n 1) (- k 1))
                (pascal-tri (- n 1) k)))))

Observe that the implementation uses the following skewed triangle for an easy formulation of the two base cases that result in 1 and 0, respectively. Of course, the triangle could be skewed to the opposite direction; but then the predicates for the base cases would need to be changed accordingly.

$\begin{array}{cccccccccc} ... &...& & & & & & & & \\ ... & 0 &...& & & & & & & \\ ... & 0 & 0 &...& & & & & & \\ ... & 0 & 1 & 0 &...& & & & & \\ ... & 0 & 1 & 1 & 0 &...& & & & \\ ... & 0 & 1 & 2 & 1 & 0 &...& & & \\ ... & 0 & 1 & 3 & 3 & 1 & 0 &...& & \\ ... & 0 & 1 & 4 & 6 & 4 & 1 & 0 &...& \\ ... &...&...&...&...&...&...&...&...&...\\ \end{array}$

Exercise 1.13 (TODO)

Prove that $\mathrm{Fib}(n)$ is the closest integer to $\phi^n/\sqrt{5}$ , where $\phi = (1 + \sqrt{5})/2$ . Hint: Let $\psi = (1 - \sqrt{5})/2$ . Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $\mathrm{Fib}(n) = (\phi^n - \psi^n) / \sqrt{5}$ .

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

Exercise 1.14 (TODO)

Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

Exercise 1.15

The sine of an angle (specified in radians) can be computed by making use of the approximation $\sin x \approx x$ if $x$ is sufficiently small, and the trigonometric identity

$\begin{equation} \sin x = 3 \sin \frac{x}{3} - 4 \sin^3 \frac{x}{3} \end{equation}$

to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered “sufficiently small” if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a. How many times is the procedure p applied when (sine 12.15) is evaluated?

5 times because of the logarithmic growth (see below) combined with 12.15 and 0.1 yields approximately 4.37:

(/ (log (/ 12.15 0.1)) (log 3))

b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

The process is recursive without branching so the order of growth in space is the same as that in the number of steps. The latter is logarithmic because at each step the input angle is divided by the constant 3.

’’ ‘’