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:
- $Fib(n)=(\phi^n-\psi^n)/\sqrt5$, where $\phi=(1+\sqrt5)/2$ and $\psi=(1-\sqrt5)/2$.
- $Fib(n)$ is the closest integer to $\phi^n/\sqrt5$.
Let $\mathcal{P}(n):Fib(n)=\frac{\phi^n-\psi^n}{\sqrt5}$. We will use induction to prove that $\mathcal{P}(n)$ is true for all $n\in\mathbb{N}$.
$\mathcal{P}(1)$ is true:
\[\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 $\mathcal{P}(n)$ be true for all $n\le k\in\mathbb{N}$. We will try to show that $\mathcal{P}(k+1)$ is also true.
By the definition of $Fib(n)$,
\[Fib(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, $\mathcal{P}(k+1)$ is true whenever $\mathcal{P}(n)$ is true for all $n\le k\in\mathbb{N}$.
$\therefore\mathcal{P}(n)$ is true for all $n\in\mathbb{N}$ by the principle of mathematical induction.
Now that we know that $Fib(n)=(\phi^n-\psi^n)/\sqrt5$, the second part is pretty straightforward.
\[\psi=\frac{1-\sqrt5}{2}\approx-0.618\]Raising $\psi$ to $n$ and then dividing it by $\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)$ is equal to the integer closest to $\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 $\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 $n$?
For $n=1$,
(cc 1 1)
(cc 1 0)
(cc 0 1)
Number of steps = $3$
For $n=2$,
(cc 2 1)
(cc 2 0)
(cc 1 1)
(cc 1 0)
(cc 0 1)
Number of steps = $5$
For $n=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 = $7$
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+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):
Proceeding with similar logic for (cc n 3), (cc n 4), and (cc n 5), here are all the five functions:
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.
$P_1(n)$ is a linear polynomial in $n$.
$P_2(n)$ can be simplified to
Substitute $\lfloor n/5\rfloor=n/5-\theta$ where $\theta\in[0,1)$.
\[P_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.}\]$P_2(n)$ is clearly a quadratic polynomial in $n$. If we proceed similarly (or just look at the $n$s inside the summations), we can discern that $P_5(n)$ will be a polynomial of degree $5$. Thus, the steps required by the process generated by the count-change procedure grow as $\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 $k$, where $k$ is the smallest integer that satisfies
We can rearrange the above inequality as,
\[10a\le3^k\\ \implies\log{10a}\le\log{3^k}\\ \implies\log{10a}\le k\log{3}\\ \implies\log_{\,3}{10a}\le k\]Since $k$ is the smallest integer that satisfies the above inequality,
\[k=\lceil\log_{\,3}{10a}\rceil\]Therefore, the space used by the process grows as $\Theta(\log{a})$.
Order of Growth of Number of Steps
The number of steps used by the generated process is equal to $2k+1$, which can be written as,
\[R(a)=2\lceil\log_{\,3}{10a}\rceil+1\]The order of growth of this function is also $\Theta(\log{a})$.