SICP Exercise Solutions - Chapter 1

I have started learning SICP since I have been bitten by the functional programming bug. Therefore, I will be adding most of the solutions to SICP exercise problems in this blog. I am using Dr.Scheme to implement these solutions.

Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

Solution:
(define (sos2ln a b c)(if (> a b)(if (> b c)(+ (sqr a) (sqr b))(+ (sqr a) (sqr c)))(if (> a c)(+ (sqr b) (sqr a))(+ (sqr b) (sqr c)))))

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.

Solution:
Recursive Process:

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

Iterative Process:

(define (f n)
  (f-iter 2 1 0 n))
(define (f-iter a b c n)
  (if (= n 0) c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))

Exercise 1.12. The following pattern of numbers is called Pascal's triangle.

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. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.
Solution:

(define (pt r c)
  (cond ((or (< r 0) (< c 0)) 0)
        ((and (= r 1) (= c 1)) 1)
        (else (+ (pt (- r 1)(- c 1))(pt (- r 1)c)))))

Exercise 1.17. The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.
Solution:

(define (even? x)
  (= (remainder x 2) 0))

(define (dbl x)
  (+ x x))

(define (half x)
  (/ x 2))

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (* (dbl a) (half b)))
        (else (+ a (* a (- b 1))))))

Exercise 1.29. Simpson's Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson's Rule, the integral of a function f between a and b is approximated as

h/3[y0+4y1+2y2+4y3+2y4+...+2yn-2+4yn-1+yn]

where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the accuracy of the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000), and compare the results to those of the integral procedure shown above.

Solution:

(define (gs term a next b)
  (if (> a b) 0
      (+ (term a) (gs term (next a) next b))))

(define (sr f a b n)
  (define h (/ (- b a) n))
  (define (inc-2h x) (+ x (* 2 h)))
  (* (/ h 3) (+ (f a) (* 2 (gs f (+ a (* 2 h)) inc-2h b)) (* 4 (gs f  (+ a (* 1 h)) inc-2h b) (f (+ a (* n h)))))))

Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:
(accumulate combiner null-value term a next b)
Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.
Solution:

(define (accumulate combiner null-value term a next b)
  (if (> a b) null-value
      (combiner (term a) (accumulate combiner null-value term (next a) next b))))

(define (sum-combiner x y)(+ x y))

(define (prod-combiner x y) (* x y))

(define (id x) x)

(define (inc x) (+ x 1))

(accumulate sum-combiner 0 id 1 inc 10)
;55
(accumulate prod-combiner 1 id 1 inc 5)
;120

Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure.
Solution:

(define (filtered-accumulate predicate combiner null-value term a next b)
  (if (> a b) null-value
      (combiner (if (predicate a) (term a) null-value) (filtered-accumulate predicate combiner null-value term (next a) next b))))

Show how to express the following using filtered-accumulate:

a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)
Solution:

(filtered-accumulate prime? sum-combiner 0 sqr 1 inc 3)

Exercise 1.37. a. An infinite continued fraction is an expression of the form
As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation -- a so-called k-term finite continued fraction -- has the form
Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/ using

(cont-frac
(lambda (i) 1.0)
(lambda (i) 1.0)
k)
for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?
b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
Solution:

Recursive:
(define (cont-frac n d k)
  (define (cont-frac-helper i)
    (if (> i k) 0
        (/ (n i) (+ (d i) (cont-frac-helper (+ i 1))))))
  (cont-frac-helper 1)
  )
Iterative:
(define (cont-frac-iter n d k)
  (define (cont-frac-helper pd k)
    (if (= k 0) pd
        (cont-frac-helper (/ (n k) (+ (d k) pd)) (- k 1))))
  (cont-frac-helper 0 k)
  )

Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

Solution:

(define (nl_denoms i)
  (cond ((=(remainder i 3) 1) 1)
        ((=(remainder i 3) 2) (final_sum (+ (quotient i 3) 1)))
        ((=(remainder i 3) 0) 1)))

(define (final_sum i)
  (define (helper i result)
    (if (= i 0) result
        (helper (- i 1) (+ result 2))))
  (helper i 0)
  )

(+ 2 (cont-frac (lambda (x) 1.0) nl_denoms 11))
;2.7182818352059925
(+ 2 (cont-frac-iter (lambda (x) 1.0) nl_denoms 11))
;2.7182818352059925