SICP Exercise 1.14 – Counting Change

The exercise asks us to draw the tree illustrating the process generated by count-change given the argument 11 cents.

The count-change procedure is given as follows:

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                   (- kinds-of-coins 1))
                 (cc (- amount
                       (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

The process tree can be laid out as follows:

(count-change 11)
(cc 11 5)
(+ (cc 11 4) (cc -39 4))
(+ (cc 11 4) 0)
(+ (+ (cc 11 3) (cc -14 4)) 0)
(+ (+ (+ (cc 11 2) (cc 1 3)) 0) 0)
(+ (+ (+ (+ (cc 11 1) (cc 6 2)) (+ (cc 1 2) (cc -9 3))) 0) 0)
(+ (+ (+ (+ (+ (cc 11 0) (cc 10 1)) (+ (cc 6 1) (cc 1 1))) (+ (+ (cc 1 1) (cc -4 2)) 0)) 0) 0)
(+ (+ (+ (+ (+ 0 (+ (cc 10 0) (cc 9 1))) (+ (+ (cc 6 0) (cc 5 1)) (+ (cc 1 0) (cc 0 1)))) (+ (+ (+ (cc 1 0) (cc 0 1)) 0) 0)) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ (cc 9 0) (cc 8 1)))) (+ (+ 0 (+ (cc 5 0) (cc 4 1))) (+ 0 1))) (+ (+ (+ 0 1) 0) 0)) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ (cc 8 0) (cc 7 1))))) (+ (+ 0 (+ 0 (+ (cc 4 0) (cc 3 1)))) 1)) (+ (+ 1 0) 0)) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 7 0) (cc 6 1)))))) (+ (+ 0 (+ 0 (+ 0 (+ (cc 3 0) (cc 2 1))))) 1)) (+ 1 0)) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 6 0) (cc 5 1))))))) (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 2 0) (cc 1 1)))))) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 5 0) (cc 4 1)))))))) (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 1 0) (cc 0 1))))))) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 4 0) (cc 3 1))))))))) (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1)))))) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 3 0) (cc 2 1)))))))))) (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1))))) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 2 0) (cc 1 1))))))))))) (+ (+ 0 (+ 0 (+ 0 (+ 0 1)))) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ (cc 1 0) (cc 0 1)))))))))))) (+ (+ 0 (+ 0 (+ 0 1))) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1))))))))))) (+ (+ 0 (+ 0 1)) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1)))))))))) (+ (+ 0 1) 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1))))))))) (+ 1 1)) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1)))))))) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1))))))) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1)))))) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 (+ 0 1))))) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 (+ 0 1)))) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 (+ 0 1))) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 (+ 0 1)) 2) 1) 0) 0)
(+ (+ (+ (+ (+ 0 1) 2) 1) 0) 0)
(+ (+ (+ (+ 1 2) 1) 0) 0)
(+ (+ (+ 3 1) 0) 0)
(+ (+ 4 0) 0)
(+ 4 0)
4

Clearly, from the above expansion, the space required grows linearly with the argument to count-change.

To calculate the order of growth as the change increases, we know that the number of coins in the denominations are a constant (5).

Now, every call to (cc n 1) leads to two calls (+ (cc n 0) (cc (- n 1) 0)) and this process keeps on continuing until n becomes 1, which belongs to O(n).

Every call to (cc n 2) leads to two calls (+ (cc n 1) (cc (- n 5) 2)). Now at every step, the argument to (cc n 2) decreases by 5 and hence a total of n/5 calls are made each of which gets attached with a (cc n 1) call which belongs to O(n). Thus, (cc n 2) belongs to $O(n^2)$ .

Now, (cc n 3) expands to (+ (cc n 2) (cc (- n 10) 3)). Similar to the above situation, n/10 calls are made each attached to a (cc n 2) call, thus belonging to $O(n^3)$ .

Similarly, (cc n 4) expands to (+ (cc n 3) (cc (- n 25) 4)), which belongs to $O(n^4)$ and (cc n 5) expands to (+ (cc n 4) (cc (- n 50) 5)) which belongs to $O(n^5)$ .

Thus, the order of growth of the procedure belongs to $O(n^5)$ .

SICP Exercise 1.12 – Pascal’s Triangle

The exercise asks us to implement a procedure that computes the elements of a Pascal’s triangle recursively.

A Pascal’s Triangle is shown in the following image:

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.

We can use the above property to construct a procedure that gives us the number located at a particular location. We can lay out the above triangle in a matrix form as follows:

We observe that each row has the same number of elements as the row number and the first and the last element of each row is 1.

The procedure can then be defined as:

(define (pascal-triangle row col)
  (cond ((> col row) -1)
        ((= col 1) 1)
        ((= col row) 1)
        (else (+ (pascal-triangle (- row 1) (- col 1)) (pascal-triangle (- row 1) col))))))

The above procedure that assumes that the matrix is 1 based and not 0 based.

SICP Exercise 1.11 – Writing a Procedure

In this exercise, we are asked to write a procedure to compute the function f:

f(n) = n, n < 3
f(n) = f(n-1) + 2*f(n-2) + 3*f(n-3), n ≥ 3

A procedure that computes f by means of a recursive process is easy and can be written as:

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

To write an iterative procedure, we observe that for the computation of $f(n)$ , only the values of $f(n-1)$ , $f(n-2)$ and $f(n-3)$ are needed. Leveraging this, we can write an iterative procedure where these three values are passed as arguments:

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

(define (f-iter n1 n2 n3 left)
  (if (= left 0) n1
      (f-iter (+ n1 (* 2 n2) (* 3 n3))
              n1
              n2
              (- left 1))))

SICP Exercise 1.10 – Ackermann’s Function

The exercise gives us a procedure to compute Ackermann’s Function (The inverse of the Ackermann’s Function appears in the analysis of the fastest non-randomized comparison based MST algorithm by Bernard Chazelle introduced in the paper A Minimum Spanning Tree Algorithm with Inverse Ackermann Type Complexity):

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

The exercise asks us to compute the values of:

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

This can be done using the Scheme Interpreter:

1 ]=> (A 1 10)

;Value: 1024

1 ]=> (A 2 4)

;Value: 65536

1 ]=> (A 3 3)

;Value: 65536

The next part asks us to give concise mathematical definitions for the following functions:

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))

Clearly, when (= x 0), the function A returns (* 2 y), so, $f(n)\,=\,2\times n$ .

And, when (= x 1),

(A 1 n)
(A 0 (A 1 (- y 1)))
(* 2 (A 1 (- y 1)))
(* 2 (A 0 (A 1 (- (- y 1) 1))))
(* 2 (A 0 (A 1 (- y 2))))
(* 2 (* 2 (A 1 (- y 2))))
...
...
...

This goes on until (= y 1), at which point 2 is returned. So, when (= n 0), then $g(n)\,=\,0$ , and otherwise $g(n)\,=\,2^n$ .

Now, for (define (h n) (A 2 n)),

(A 2 n)
(A (- 2 1) (A 2 (- n 1)))
(A 1 (A 2 (- n 1)))

Clearly, (A 2 (- n 1)) is equivalent to (h (- n 1)), and (A 1 (h (- n 1))) is equivalent to $2^{h(n-1)}$ (from the definition of $g(n)$ ). So,

$h(n)\,=\,2^{h(n-1)}$ for $n \geq 2$
$h(1)\,=\,2$
$h(0)\,=\,0$

SICP Exercise 1.9 – Illustrating the Process

The exercise asks us to use the substitution model to evaluate the expression (+ 4 5), using the two different variations of + as given below:

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

where inc and dec increase and reduce its arguments by 1, respectively.

Using the first procedure, we can evaluate (+ 4 5) as follows: (Ignoring the evaluation of the if expression)

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

Clearly, the first procedure is a recursive procedure.

For the second procedure, the evaluation proceeds as follows:

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

Clearly, this is an iterative procedure.

SICP Exercise 1.8 – Newton’s Method For Cube Roots

The exercise asks us to implement Newton’s method for finding cube roots.

Newton’s method says that if y is an approximation to the cube root of x, then a better approximation is given by the value:
$\frac{\frac{x}{y^2} + 2y}{3}$

We can use the procedure good-enough?, that we developed in the last exercise.

(define (good-enough? guess prev_guess) 
              (< (abs (/ (- guess prev_guess) guess)) 0.00001))

We need to re-write the improve procedure to use the formula for cube roots.

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

Now, the cube-root procedure can be written as:

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

(define (cube-root x) (cbrt-iter 0.0 1.0 x))

SICP Exercise 1.7 – Problems with good-enough?

This exercise asks us to explain why the good-enough? procedure fails for small and large numbers.

For small numbers, this can be seen by running the code

(sqrt 0.0004)

which gives a value of 0.03540088, whose square 0.0012532223047744002, is within 0.001 of our given value.

0.0012532223047744002 - 0.0004 = 0.0008532223047744002
0.0008532223047744002 < 0.001

For very large numbers, the code never stops running. For example,

(sqrt 9898989898989898)

never stops running. This is because floats have a fixed precision. After a certain point, the guesses are unable to guess the square root of a number within 0.001 of the answer. At that point, they alternate between the two guesses, both of whose squares are more than 0.001 away from the argument.

This problem can be seen in Python too, which stops, but returns the wrong answer for the square root.

>>> val = 9898989898989898
>>> val ** 0.5
99493667.6326182
>>> _ ** 2
9898989898989900.0
>>> _ - val
2.0

The question proposes an alternative to the earlier procedure. It asks us to watch how guess changes from one iteration to another and to stop when the change is a very small fraction of the guess.

(define (good-enough? guess prev_guess) 
              (< (abs (/ (- guess prev_guess) guess)) 0.001))
(define (average x y) (/ (+ x y) 2))
(define (improve guess x) (average guess (/ x guess)))
(define (sqrt-iter prev_guess guess x)
        (if (good-enough? guess prev_guess) guess
            (sqrt-iter guess (improve guess x) x)))
(define (sqrt x) (sqrt-iter 0.0 1.0 x))

Running the above version on our example 0.0004, gave the result 2.0000000050877154e-2, which is very close to the square root of 0.0004. But, for the other example,

1 ]=> (sqrt 9898989898989898)
;Value: 99493667.71674988

1 ]=> (square 99493667.71674988)
;Value: 9898989915731036.

1 ]=> (- 9898989898989898 9898989915731036)
;Value: -16741138

which is a huge difference. We can achieve by refining the factor in good-enough?

(define (good-enough? guess prev_guess) 
              (< (abs (/ (- guess prev_guess) guess)) 0.00001))

which gives us the results:

1 ]=> (sqrt 0.0004)
;Value: .02

1 ]=> (sqrt 9898989898989898)
;Value: 99493667.63261819

1 ]=> (square 99493667.63261819)
;Value: 9898989898989900.

1 ]=> (- 9898989898989898 9898989898989900)
;Value: -2

Audacity Fails with the Pa_GetStreamHostApiType Error.

EDIT – Look for a better way to do this at the end of the post.

I was just running some PortAudio programs, when I saw that the maximum and the average amplitude reported by the recording were both 0.00. This meant that my microphone was not working and I immediately tried to start Audacity to test whether that was the case, since it gives a beautiful wave form for the recording in real time.

Running Audacity using GUI on Ubuntu 12.04 LTS, it failed to start and I tried restarting it a couple of times. Then, I went to the terminal and tried to start Audacity from there, at which point, it failed with the error:

audacity: symbol lookup error: audacity: undefined symbol: Pa_GetStreamHostApiType

Seeing the undefined symbol, Pa_GetStreamHostApiType, I knew that my PortAudio installation had messed something up.

So, to see the shared library dependencies of Audacity, I did:

ldd /usr/bin/audacity | grep portaudio

and sure enough, the dependency was pointing to /usr/local/lib.

So, the solution was to remove the libportaudio files from the /usr/local/lib, by doing:

rm -rf /usr/local/lib/libportaudio*
ldconfig

And, then I tried running Audacity and it finally started!

Another way to get your Audacity installation up and running without deleting shared libraries would be to give Audacity an extra directory to look for the libportaudio.so.* files. This is done using the LD_LIBRARY_PATH variable. Here’s a blog post explaining why LD_LIBRARY_PATH is bad.

Start Audacity using the following command then:

LD_LIBRARY_PATH=/usr/lib/x86_64-linux-gnu/ audacity

If anyone cares, the reason why I wasn’t getting any input through the microphone was that somehow the Microphone had gotten muted inside the Sound Settings of Ubuntu!

I had to set it back to Unamplified and the microphones were back to life again!

Input Volume; Unamplified

SICP Exercise 1.6 – A New Version of if

In this exercise, we are given a procedure called new-if which tries to implement an if condition using cond expressions.

(define (new-if predicate then-clause else-clause)
    (cond (predicate then-clause)
          (else else-clause)))

Now, the square root program is re-written to use the new-if procedure,

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

Running this with (sqrt-iter 1.0 4), we get

This is because an if expression is evaluated differently than what is being described by the new-if procedure. From The Scheme Docs – Section 2.7 – Conditionals,

An if expression is evaluated as follows: first, predicate is evaluated. If it yields a true value, then consequent is evaluated and its value is returned. Otherwise alternative is evaluated and its value is returned. If predicate yields a false value and no alternative is specified, then the result of the expression is unspecified.

But, since Scheme uses applicative-order evaluation, the operands of the new-if procedure are evaluated first and then their values are applied in the expressions.

So, every call to sqrt-iter recursively calls itself by passing an expression calling sqrt-iter to the new-if expression.

if expressions work differently by evaluating the predicate first and then deciding whether to evaluate the consequent or the alternative.

SICP Exercise 1.5 – Ben Bitdiddle’s Test

This exercise introduces us to the character of Ben Bitdiddle and his invention of a test to determine whether the given interpreter is using applicative-order evaluation or normal-order evaluation.

In Normal-Order Evaluation, the operands are not evaluated until their value is needed and the operand expressions are substituted in parameters until an expression with only a primitive operation is reached.

On the other hand, in Applicative-Order Evaluation, the arguments are evaluated first and then these values are substituted in further expressions.

Ben Bitdiddle has come up with two procedures for his test:

(define (p) (p))

(define (test x y)
     (if (= x 0) 0
         y))

The first procedure

(define (p) (p))

defines a procedure which calls itself without a base case. Evaluating this procedure in the interpreter does not return anything because the procedure recursively calls itself and never stops.

Now, Ben evaluates the expression

(test 0 (p))

In applicative order evaluation, the operands are evaluated first and so, when evaluating (p), the interpreter would never return and nothing would be given as output.

On the other hand, in normal order evaluation, the operands are not evaluated until their values are needed. So, evaluating the expression (test 0 (p)) leads to

(test 0 (p))
(if (= 0 0) 0 (p))
0

Since the predicate (= 0 0) evaluates to #t, so, the consequent 0 is returned and the alternative (p) is never evaluated and the interpreter never gets stuck in the recursion.

	Audacity won’t… on Audacity Fails with the Pa_Get…
	Random Human on SICP Exercise 1.4 – Comp…
	Sukrit Kalra on SICP Exercise 1.4 – Comp…
	Random Human on SICP Exercise 1.7 – Prob…
	Random Human on SICP Exercise 1.4 – Comp…