Akshath's Blog
Back to archive
•
5 min read
SICP Exercises 1.11 - 1.15

This post contains my solutions to some exercises from the book “Structure and Interpretation of Computer Programs” that I’m reading as part of my “Learning Computer Science” project. You can find an online version of the text at the companion website for the book.

Exercise 1.11

Procedure that generates a recursive process:

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

Procedure that generates an iterative process:

(define (f n)
  (define (iter i fi1 fi2 fi3)
    (if (= i (+ n 1))
      fi1
      (iter (+ i 1)
        (+ fi1 (* 2 fi2) (* 3 fi3))
        fi1
        fi2)))
  (if (< n 3)
    n
    (iter 3 2 1 0)))

Exercise 1.12

(define (pte row col)
  (cond ((= col 1) 1)
    ((= row col) 1)
    ((< row col) 0)
    (else (+ (pte (- row 1) (- col 1))
            (pte (- row 1) col)))))

Exercise 1.13

To prove:

  1. Fib(n)=(ϕn−ψn)/5Fib(n)=(\phi^n-\psi^n)/\sqrt5, where ϕ=(1+5)/2\phi=(1+\sqrt5)/2 and ψ=(1−5)/2\psi=(1-\sqrt5)/2.
  2. Fib(n)Fib(n) is the closest integer to ϕn/5\phi^n/\sqrt5.

Let P(n):Fib(n)=ϕn−ψn5\mathcal{P}(n):Fib(n)=\frac{\phi^n-\psi^n}{\sqrt5}. We will use induction to prove that P(n)\mathcal{P}(n) is true for all n∈Nn\in\mathbb{N}.

P(1)\mathcal{P}(1) is true:

LHS=Fib(1)=1RHS=ϕ−ψ5=1+52−1−525=1LHS=RHS\text{LHS}=Fib(1)=1\\ \text{RHS}=\frac{\phi-\psi}{\sqrt5}=\frac{\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}}{\sqrt5}=1\\ \text{LHS}=\text{RHS}

Now, let P(n)\mathcal{P}(n) be true for all n≤k∈Nn\le k\in\mathbb{N}. We will try to show that P(k+1)\mathcal{P}(k+1) is also true.

By the definition of Fib(n)Fib(n),

Fib(k+1)=Fib(k)+Fib(k−1)  ⟹  Fib(k+1)=ϕk−ψk5+ϕk−1−ψk−15  ⟹  Fib(k+1)=ϕk−1(ϕ+1)−ψk−1(ψ+1)5  ⟹  Fib(k+1)=ϕk−1(ϕ2)−ψk−1(ψ2)5  ⟹  Fib(k+1)=ϕk+1−ψk+15Fib(k+1) = Fib(k) + Fib(k-1)\\ \implies Fib(k+1) = \frac{\phi^k-\psi^k}{\sqrt5} + \frac{\phi^{k-1}-\psi^{k-1}}{\sqrt5}\\ \implies Fib(k+1) = \frac{\phi^{k-1}(\phi+1)-\psi^{k-1}(\psi+1)}{\sqrt5}\\ \implies Fib(k+1) = \frac{\phi^{k-1}(\phi^2)-\psi^{k-1}(\psi^2)}{\sqrt5}\\ \implies Fib(k+1) = \frac{\phi^{k+1}-\psi^{k+1}}{\sqrt5}

Thus, P(k+1)\mathcal{P}(k+1) is true whenever P(n)\mathcal{P}(n) is true for all n≤k∈Nn\le k\in\mathbb{N}.
∴P(n)\therefore\mathcal{P}(n) is true for all n∈Nn\in\mathbb{N} by the principle of mathematical induction.

Now that we know that Fib(n)=(ϕn−ψn)/5Fib(n)=(\phi^n-\psi^n)/\sqrt5, the second part is pretty straightforward.

ψ=1−52≈−0.618\psi=\frac{1-\sqrt5}{2}\approx-0.618

Raising ψ\psi to nn and then dividing it by 5\sqrt5 will result in very small quantities. For example,

psi = (1-5**0.5)/2
print([round(psi**i/5**0.5, 4) for i in list(range(1, 11))]))
[-0.2764, 0.1708, -0.1056, 0.0652, -0.0403, 0.0249, -0.0154, 0.0095, -0.0059, 0.0036]

∴\therefore ψ\psi can be neglected and Fib(n)Fib(n) is equal to the integer closest to ϕn5\frac{\phi^n}{\sqrt5}.

Exercise 1.14

Tree illustrating the process generated by the count-change procedure in making change for 11 cents:

(cc 11 5)
  (cc 11 4)
    (cc 11 3);  number of ways of changing 11 with 10s, 5s, and 1s [4 ways: (10+1) and 👇]
      (cc 11 2);  number of ways of changing 11 with 5s and 1s [3 ways: (5+5+1), (5+1+1+1+1+1+1) and 👇]
        (cc 11 1);  number of ways of changing 11 with 1s [1 way: (1+1+1+1+1+1+1+1+1+1+1)]
          (cc 11 0)
            0
          (cc 10 1)
            (cc 10 0)
              0
            (cc 9 1)
              (cc 9 0)
                0
              (cc 8 1)
                (cc 8 0)
                  0
                (cc 7 1)
                  (cc 7 0)
                    0
                  (cc 6 1)
                    (cc 6 0)
                      0
                    (cc 5 1)
                      (cc 5 0)
                        0
                      (cc 4 1)
                        (cc 4 0)
                          0
                        (cc 3 1)
                          (cc 3 0)
                            0
                          (cc 2 1)
                            (cc 2 0)
                              0
                            (cc 1 1)
                              (cc 1 0)
                                0
                              (cc 0 1)
                                1
        (cc 6 2)
          (cc 6 1)
            (cc 6 0)
              0
            (cc 5 1)
              (cc 5 0)
                0
              (cc 4 1)
                (cc 4 0)
                  0
                (cc 3 1)
                  (cc 3 0)
                    0
                  (cc 2 1)
                    (cc 2 0)
                      0
                    (cc 1 1)
                      (cc 1 0)
                        0
                      (cc 0 1)
                        1
          (cc 1 2)
            (cc 1 1)
              (cc 1 0)
                0
              (cc 0 1)
                1
            (cc -4 2)
              0
      (cc 1 3)
        (cc 1 2)
          (cc 1 1)
            (cc 1 0)
              0
            (cc 0 1)
              1
          (cc -4 2)
            0
        (cc -9 3)
          0
    (cc -14 4)
      0
  (cc -39 5)
    0

Order of Growth of Space

As in the case of the tree-recursive Fibonacci computation,

“…the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation.”

the order of growth of space is given by Θ(n)\Theta(n).

Order of Growth of Number of Steps

We are supposed to find out the order of growth of the number of steps as the amount to be changed increases. First, let’s break the problem down into smaller steps.

Suppose we only had coins of denomination 1. How many steps would it take to change an amount nn?

For n=1n=1,

(cc 1 1)
  (cc 1 0)
  (cc 0 1)

Number of steps = 33

For n=2n=2,

(cc 2 1)
  (cc 2 0)
  (cc 1 1)
    (cc 1 0)
    (cc 0 1)

Number of steps = 55

For n=3n=3,

(cc 3 1)
  (cc 3 0)
  (cc 2 1)
    (cc 2 0)
    (cc 1 1)
      (cc 1 0)
      (cc 0 1)

Number of steps = 77

In general,

(cc n 1)
  (cc n 0)
  (cc n-1 1)
    (cc n-1 0)
    (cc n-2 1)
      ...
        (cc 1 0)
        (cc 0 1)

Number of steps = 2n+12n+1

Now, suppose we also had coins of denomination 5. Then, the tree for the process generated when (cc n 2) is called would look like:

(cc n 2)
  (cc n 1); this takes 2*n + 1 steps
  (cc n-5 2)
    (cc n-5 1); this takes 2*(n-5) + 1 steps
    (cc n-10 2)
      ...

After a bit of trial and error, and comparing values with the output of the following C++ code…

#include <bits/stdc++.h>

using namespace std;

int first_denomination(int n){
    switch(n){
        case 1: return 1;
        case 2: return 5;
        case 3: return 10;
        case 4: return 25;
        case 5: return 50;
        default: return 0;
    }
}

int cc(int amount, int kc, int &calls){
    ++calls;
    if (amount == 0) return 1;
    else if (amount < 0 || kc == 0) return 0;
    else return cc(amount, kc - 1, calls) + cc(amount - first_denomination(kc), kc, calls);
}

int main(){
    for (int i = 0; i <= 15; ++i){
        int calls = 0;
        cc(i, 5, calls);
        cout << i << ": " << calls << '\n';
    }
    return 0;
}

…I worked out the following function to compute the number of steps taken by (cc n 2):

f(n)=∑k=0⌊n/5⌋(2(n−5k)+1)+⌊n/5⌋+{0if 5 divides n2otherwisef(n)=\sum_{k=0}^{\lfloor n/5\rfloor}(2(n-5k)+1)+\lfloor n/5\rfloor + {\left\lbrace\begin{matrix}{0}&{\text{if 5 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}

Proceeding with similar logic for (cc n 3), (cc n 4), and (cc n 5), here are all the five functions:

P1(n)=2n+1P2(n)=∑k=0⌊n/5⌋P1(n−5k)+⌊n/5⌋+{0if 5 divides n2otherwiseP3(n)=∑k=0⌊n/10⌋P2(n−10k)+⌊n/10⌋+{0if 10 divides n2otherwiseP4(n)=∑k=0⌊n/25⌋P3(n−25k)+⌊n/25⌋+{0if 25 divides n2otherwiseP5(n)=∑k=0⌊n/50⌋P4(n−50k)+⌊n/50⌋+{0if 50 divides n2otherwiseP_1(n)=2n+1 \\ P_2(n)=\sum_{k=0}^{\lfloor n/5\rfloor}P_1(n-5k)+\lfloor n/5\rfloor + {\left\lbrace\begin{matrix}{0}&{\text{if 5 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}\\ P_3(n)=\sum_{k=0}^{\lfloor n/10\rfloor}P_2(n-10k)+\lfloor n/10\rfloor + {\left\lbrace\begin{matrix}{0}&{\text{if 10 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}\\ P_4(n)=\sum_{k=0}^{\lfloor n/25\rfloor}P_3(n-25k)+\lfloor n/25\rfloor + {\left\lbrace\begin{matrix}{0}&{\text{if 25 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}\\ P_5(n)=\sum_{k=0}^{\lfloor n/50\rfloor}P_4(n-50k)+\lfloor n/50\rfloor + {\left\lbrace\begin{matrix}{0}&{\text{if 50 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}\\

Based on these definitions, we can write a single recursive function to compute the number of steps of the generated process. I wrote it in C++ first, because that’s what I’m most comfortable with, and then in Scheme.

int no_of_steps(int amount, int kinds_of_coins){
    if (kinds_of_coins == 1) return 2*amount + 1;
    int den = first_denomination(kinds_of_coins);
    int result = 0;
    for (int i=0; i<=amount/den; ++i)
        result += no_of_steps(amount - den*i, kinds_of_coins - 1);
    result += amount/den + (amount%den==0?0:2);
    return result;
}
(define (no-of-steps amount kinds-of-coins)
    (define den (first-denomination kinds-of-coins))
    (define (iter index result)
        (if (> index (truncate (/ amount den)))
            result
            (iter (+ index 1)
                  (+ result (no-of-steps (- amount (* den index)) 
                                         (- kinds-of-coins 1))))))
    
    (if (= kinds-of-coins 1)
        (+ (* 2 amount) 1)
        (+ (iter 0 0)
           (truncate (/ amount den))
           (if (= (remainder amount den) 0) 0 2))))

Now that we have the function definitions required to compute the number of steps for this process, it should be easy to predict what would happen if we increase the amount to be changed.

P1(n)P_1(n) is a linear polynomial in nn.
P2(n)P_2(n) can be simplified to

P2(n)=(2n+1)⌊n/5⌋−5(1+2+⋯+⌊n/5⌋)+⌊n/5⌋+{0if 5 divides n2otherwiseP_2(n)=(2n+1)\lfloor n/5\rfloor-5(1+2+\dots+\lfloor n/5\rfloor)+\lfloor n/5\rfloor+{\left\lbrace\begin{matrix}{0}&{\text{if 5 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}

Substitute ⌊n/5⌋=n/5−θ\lfloor n/5\rfloor=n/5-\theta where θ∈[0,1)\theta\in[0,1).

P2(n)=(2n+1)(n/5−θ)−5(1+2+⋯+(n/5−θ))+(n/5−θ)+{0if 5 divides n2otherwiseP_2(n)=(2n+1)(n/5-\theta)-5(1+2+\dots+(n/5-\theta))+(n/5-\theta)+{\left\lbrace\begin{matrix}{0}&{\text{if 5 divides n}}\\ 2&{\text{otherwise}}\end{matrix}\right.}

P2(n)P_2(n) is clearly a quadratic polynomial in nn. If we proceed similarly (or just look at the nns inside the summations), we can discern that P5(n)P_5(n) will be a polynomial of degree 55. Thus, the steps required by the process generated by the count-change procedure grow as Θ(n5)\Theta(n^5).

Exercise 1.15

(a)

(sine 12.15)
  (p (sine 4.05))
  (p (p (sine 1.35)))
  (p (p (p (sine 0.45))))
  (p (p (p (p (sine 0.15)))))
  (p (p (p (p (p (sine 0.05))))))
  (p (p (p (p (p 0.05)))))

The procedure p is applied 5 times when (sine 12.15) is evaluated.

(b)

Order of Growth of Space

(sine a)
  (p (sine a/3))
  (p (p (sine a/9)))
  (p (p (p (sine a/27))))
  ...
  (p (p (p ... (p (sine a/3^k)))))

Based on the definition of the sine and p procedures, the space used by the generated process (i.e., the length of the chain of deferred operations and the information needed to keep track of it) is proportional to kk, where kk is the smallest integer that satisfies

a3k≤0.1\frac{a}{3^k}\le0.1

We can rearrange the above inequality as,

10a≤3k  ⟹  log⁡10a≤log⁡3k  ⟹  log⁡10a≤klog⁡3  ⟹  log⁡ 310a≤k10a\le3^k\\ \implies\log{10a}\le\log{3^k}\\ \implies\log{10a}\le k\log{3}\\ \implies\log_{\,3}{10a}\le k

Since kk is the smallest integer that satisfies the above inequality,

k=⌈log⁡ 310a⌉k=\lceil\log_{\,3}{10a}\rceil

Therefore, the space used by the process grows as Θ(log⁡a)\Theta(\log{a}).

Order of Growth of Number of Steps

The number of steps used by the generated process is equal to 2k+12k+1, which can be written as,

R(a)=2⌈log⁡ 310a⌉+1R(a)=2\lceil\log_{\,3}{10a}\rceil+1

The order of growth of this function is also Θ(log⁡a)\Theta(\log{a}).