SICP Exercise Solutions - Chapter 2

Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:
Solution:

(define (make-point x y)
  (cons x y))

(define (x-point p)
  (car p))

(define (y-point p)
  (cdr p))

(define (make-segment p1 p2)
  (cons p1 p2))

(define (start-segment s)
  (car s))

(define (end-segment s)
  (cdr s))

(define (midpoint-segment ls)
  (make-point 
               (avg (x-point (start-segment ls)) (x-point (end-segment ls)))
               (avg (y-point (start-segment ls)) (y-point (end-segment ls)))
               ))

(define (avg x y)
  (/ (+ x y) 2))

;Test Data
(define p1 (make-point 4 6))
(define p2 (make-point 8 18))
(define ls (make-segment p1 p2))
(midpoint-segment ls)
;6 12

Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))

Solution:

(define (rev items)
  (define (helper items rl)
    (if (null? items) rl
        (helper (cdr items) (cons (car items) rl))))
  (helper items null))

(define (deep-rev items)
  (define (helper ritems)
  (if (null? ritems)
      null
      (cons (if (not (pair? (car ritems))) (car ritems)(rev(car ritems))) (helper (cdr ritems)))))
  (helper (rev items)))

Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)

Solution:

(define (fringe items)
  (cond ((null? items) null)
        (else (append (if (not (pair? (car items))) (list (car items)) (car items)) (fringe (cdr items))))))

(define (deep-fringe items)
  (if (not (exists-pair? items))
      items
      (deep-fringe (fringe items))))

(define (exists-pair? items)
  (cond ((null? items) #f)
        ((pair? (car items)) #t)
        (else (exists-pair? (cdr items)))))

Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

(define (make-mobile left right)
  (list left right))

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

(define (make-branch length structure)
  (list length structure))

a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.
b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
d. Suppose we change the representation of mobiles so that the constructors are

(define (make-mobile left right)
  (cons left right))
(define (make-branch length structure)
  (cons length structure))

How much do you need to change your programs to convert to the new representation?
Solution:
a)

(define (make-branch len st)
  (list len st))
(define (make-mobile lb rb)
  (list lb rb))
(define (left-branch m)
  (car m))
(define (right-branch m)
  (car (cdr m)))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (car (cdr b)))

b)

(define (mobile? m)
  (pair? m))

(define (total-weight m)
  (cond ((null? m) 0)
        ((not (mobile? m)) m)
        (else (+ (total-weight (branch-structure (left-branch m)))
                 (total-weight (branch-structure (right-branch m)))))))
;Test
(define lb3 (make-branch 2 1))
(define rb3 (make-branch 1 2))
(define mb3 (make-mobile lb3 rb3))
(define lb2 (make-branch 3 mb3))
(define rb2 (make-branch 9 1))
(define mb2 (make-mobile lb2 rb2))
(define lb1 (make-branch 4 mb2))
(define rb1 (make-branch 8 2))
(define mb1 (make-mobile lb1 rb1))

(total-weight mb3)
(total-weight mb2)
(total-weight mb1)

d)

(define (make-branch len st)
  (cons len st))
(define (make-mobile lb rb)
  (cons lb rb))
(define (left-branch m)
  (car m))
(define (right-branch m)
  (cdr m))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (cdr b))

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