Concrete Abstractions: Chapter 2

At the moment I’m working through Concrete Abstractions which is so far pretty great. I enjoy the writing style and the difficulty of the exercises. You can buy a used copy for about 10 bucks or read it for free online.

I’m going to present solutions to some exercises. However, I recommend working through this book by yourself. You’ll learn a lot!

Exercise 2.9 Write a procedure that computes the number of 6s in the decimal representation of an integer. Generalize this to a procedure that computes the number of d’s, where d is another argument.

Solution: Idea behind this algorithm is to find the last digit, evaluate it and shorten the number by one digit. You can achieve the first one by taking the reminder of the number n and 10. For example: Reminder of $151 / 10 = 1$ , because $151 / 10 = 15.1 \implies 0.1 * 10 = 1$ .
The last thing to do is to shorten the number. It’s easy done by subtracting the reminder of the number and dividing it by ten: $151 - 1 = 150 \implies 150 / 10 = 15$

(define (num-of-d n d)
  (if (< n 10)
    (if (= n d)
      1
      0)
    (+ (if (= d (remainder n 10))
      1
      0)
       (num-of-d (/ (- n (remainder n 10)) 10) d))))

Exercise 2.12 Any positive integer $i$ can be expressed as $i=2^nk$ , where $k$ is odd, that is, as a power of 2 times an odd number. We call $n$ the exponent of 2 in $i$ . For example, the exponent of 2 in 40 is 3 (because $40 = 2^35$ ) whereas the exponent of 2 in 42 is 1. If i itself is odd, then n is zero. If, on the other hand, i is even, that means it can be divided by 2. Write a procedure for finding the exponent of 2 in its argument.

Solution: The trick here is quite easy. We know that $k$ needs to be an integer. I just test this by comparing the results of $i / 2^n$ . Furthermore, I calculated a upper limit for n which equals $\log_2 (i)$ . If you choose the smallest positive $k$ , i.e. 1 then $i = 2^n*1 \implies \log_2 i = n$ . This makes the implementation in Scheme a bit more convenient.

(define (find-n i)
  (find-n-iter i (round (/ (log i) (log 2)))))

(define (find-n-iter i n)
  (if (= (/ i (expt 2 n)) (round (/ i (expt 2 n))))
    n
    (find-n-iter i (- n 1))))

Exercise 2.16 Consider the following procedure foo:

(define foo
  (lambda (x n)
    (if (= n 0)
      1
      (+ (expt x n) (foo x (- n 1))))))

Use induction to prove that (foo x n) terminates with the value $\frac{x^{n+1} - 1}{x-1}$
for all values of $x \neq 1$ and for all integers $n \geq 0$ . You may assume that expt works correctly, (i.e., (expt b m) returns $b^m$ ).

Info: I show a inductive proof a bit more verbose in the following exercise.

Solution: The base case is $foo(x, 0) = \frac{x^{0+1} - 1}{x-1} = 1$ .
We assume that $foo(x, n) = \frac{x^{n+1} - 1}{x-1}$ .
Therefore $foo(x, n+1) = x^{n+2} + foo(x, n)$ which is $foo(x, n+1) = x^{n+2} + \frac{x^{n+1} - 1}{x-1}$
$= \frac{x^{n+2}(x-1)}{x-1} + \frac{x^{n+1} - 1}{x-1} = \frac{x^{n+1}(x-1) + x^{n+1} - 1}{x-1} = \frac{x^{n+2} - 1}{x-1}.$

Exercise 2.18 Prove by induction that for every nonnegative integer n the following procedure computes 2n:

(define f (lambda (n)
  (if (= n 0)
    0
    (+ 2 (f (- n 1))))))

Solution: At first look at the definition. $f(0) = 0$ and $f(n) = 2 + f(n-1)$ .
Now we test the base case: $f(0) = 2*0 = 0$ which is true.
The inductive step is $f(n+1) = 2 + f(n)$ where we assume that $f(n) = 2n$ . Therefore $f(n+1) = 2 + 2n = 2(1+n).$

Exercise 2.20 Prove that the following procedure computes $n/(n+1)$ for any nonnegative integer $n$ . That is, (f n) computes $n/(n+1)$ for any integer $n \geq 0.$

(define f (lambda (n)
  (if (= n 0)
    0
    (+ (f (- n 1))
       (/ 1 (* n (+ n 1)))))))

Solution: The function is defined as $f(0) = 0$ and $f(n) = f(n-1) + \frac{1}{n * (n+1)}$ . First we test the base case. $f(0) = 0/(0+1) = 0$ . Afterwards the inductive step:
$f(n+1) = f(n) + \frac{1}{(n+1) * ((n+1)+1)}$ where we assume that $f(n) = n/(n+1)$ . Therefore, $f(n+1) = \frac{n}{n+1} + \frac{1}{(n+1) * ((n+1)+1)} = \frac{n(n+2)+1}{(n+1)(n+2)} = \frac{n^2+2n+1}{(n+1)(n+2)}.$ You can see that the numerator is the first binomial formula: $\frac{(n+1)^2}{(n+1)(n+2)} = \frac{(n+1)}{(n+2)} = \frac{n+1}{(n+1) + 1}.$