my attempt to do the exercises in sicp.

Monday, December 27, 2010

sicp exercise 3.68



;; Exercise 3.68.  Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S0,T0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:

;(define (pairs s t)
;  (interleave
;   (stream-map (lambda (x) (list (stream-car s) x))
;               t)
;   (pairs (stream-cdr s) (stream-cdr t))))
;
;Does this work? Consider what happens if we evaluate (pairs integers integers) using Louis's definition of pairs.


;; Answer: This way, the problem cannot be cleanly decomposed recursively into smaller parts like shown in the example,
;;         and since the second pairs being invoked from body f pairs, is not a part of a cons-stream, so it will be evaluated immedialtely instead of being delayed. which leads to an infinite loop.

;; replacing this definition of pairs in the previous exercise leads to:

;; Answer:
;Loading "sicp_prob_03.68.scm"... aborted
;Aborting!: maximum recursion depth exceeded



Wednesday, December 22, 2010

sicp exercise 3.67



;; Exercise 3.67.  Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i,j) (without the condition i < j). Hint: You will need to mix in an additional stream.


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (internal 0))


(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (interleave
     (stream-map (lambda(x)(list x (stream-car t)))
                 (stream-cdr s))
     (pairs (stream-cdr s) (stream-cdr t))))))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))

(define int-pairs (pairs integers integers))

(newline)

(display-stream int-pairs 20)

;; Answer:
;Loading "sicp_prob_03.67.scm"...
;(1 1)
;(1 2)
;(2 1)
;(1 3)
;(2 2)
;(1 4)
;(3 1)
;(1 5)
;(2 3)
;(1 6)
;(4 1)
;(1 7)
;(3 2)
;(1 8)
;(5 1)
;(1 9)
;(2 4)
;(1 10)
;(6 1)
;(1 11)
;(3 3)
;... done


sicp exercise 3.66



;; Exercise 3.66.  Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)

(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (internal 0))


(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

(define (integers-from-n n)
  (cons-stream n (integers-from-n (+ 1 n))))

(define integers (integers-from-n 1))

(define int-pairs (pairs integers integers))

(newline)

(display-stream int-pairs 10)

;; Felt bogged down, so ran the program to find the answer
;Loading "sicp_prob_03.66.scm"...
;(1 1)
;(1 2)
;(2 2)
;(1 3)
;(2 3)
;(1 4)
;(3 3)
;(1 5)
;(2 4)
;(1 6)
;(3 4)
;... done


Tuesday, December 21, 2010

sicp exercise 3.65



;; Exercise 3.65.  Use the series



;; to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?


(define count 0)

(define (euler-transform s)
  (let ((s0 (stream-ref s 0))           ; Sn-1
        (s1 (stream-ref s 1))           ; Sn
        (s2 (stream-ref s 2)))          ; Sn+1
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))

(define (make-tableau transform s)
  (cons-stream s
               (make-tableau transform
                             (transform s))))

(define (accelerated-sequence transform s)
  (stream-map stream-car
              (make-tableau transform s)))

(define (partial-sums s)
  (define result (cons-stream (stream-ref s 0)
                              (add-streams (stream-cdr s) result)))
   result)

(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define (stream-limit stream tolerance)
  (define (iter initial-value str)
    (let ((s (stream-car str)))
      (if (> tolerance (abs (- s initial-value))) s
          (iter s (stream-cdr str)))))
  (iter (stream-car stream) (stream-cdr stream)))
(define (incr n)
  (set! count (+ count 1))
  (+ 1 n))
(define (ln-2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (ln-2-summands (incr n)))))
(define ln-2-stream
  (partial-sums (ln-2-summands 1)))

(define acc-ln-2-stream (accelerated-sequence euler-transform (partial-sums (ln-2-summands 1))))
(newline)

;; Value of ln 2 from wolfram alpha:
;;0.6931471805599453094172321214581765680755001343602552541206...

(display (stream-limit ln-2-stream 0.0001))(newline)
(display count)(newline)
(set! count 0)
(display (stream-limit acc-ln-2-stream 0.00001))(newline)
(display count)(newline)

;; Output:
;Loading "sicp_prob_03.65.scm"...
;.6930971830599583
;9999
;.6931471960735491
;8
;... done


sicp exercise 3.64



;; Exercise 3.64.  Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by

;; (define (sqrt x tolerance)
;;   (stream-limit (sqrt-stream x) tolerance))

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

(define (sqrt-improve guess x)
  (average guess (/ x guess)))

(define (sqrt-stream x)
  (define guesses
    (cons-stream 1.0
                 (stream-map (lambda (guess)
                               (sqrt-improve guess x))
                             guesses)))
  guesses)

(define (stream-limit stream tolerance)
  (define (iter initial-value str)
    (let ((s (stream-car str)))
      (if (> tolerance (abs (- s initial-value))) s
          (iter s (stream-cdr str)))))
  (iter (stream-car stream) (stream-cdr stream)))

(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))

(newline)
(display (sqrt 30000 0.0000000000003))(newline)

;;Output:
;Loading "sicp_prob_03.64.scm"...
;173.20508075688772
;... done


sicp exercise 3.63


;;Exercise 3.63.  Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:

;;(define (sqrt-stream x)
;;  (cons-stream 1.0
;;               (stream-map (lambda (guess)
;;                             (sqrt-improve guess x))
;;                           (sqrt-stream x))))
;;
;;Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?


;; Answer:
;; The version presented above doesnt work on the already created stream, it starts creating stream right from the beginning for every iteration of the computation. This method is of same efficiency as the version of delay without memo-proc.

sicp exercise 3.62



;; Exercise 3.62.  Use the results of exercises 3.60 and 3.61 to define a procedure div-series that divides two power series. Div-series should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then div-series should signal an error.) Show how to use div-series together with the result of exercise 3.59 to generate the power series for tangent.


(define (integrate-series s)
  (define (integrate-series-i s n)
    (cons-stream  (/ (stream-car s) n)
                  (integrate-series-i (stream-cdr s) (+ 1 n))))
  (integrate-series-i s 1))

(define (mul-stream s1 s2)
  (stream-map * s1 s2))

(define minus-one
  (cons-stream -1 minus-one))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (add-streams s1 s2)
  (cons-stream (+ (stream-car s1) (stream-car s2))
               (add-streams (stream-cdr s1)(stream-cdr s2))))

(define (mul-series s1 s2)
  (cons-stream
    (* (stream-car s1)
       (stream-car s2))
    (add-streams
       (add-streams (scale-stream (stream-cdr s1) (stream-car s2))
                    (scale-stream (stream-cdr s2) (stream-car s1)))
       (cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2))))))

(define (invert-unit-series s)
  (define X
    (cons-stream 1 (mul-stream minus-one (mul-series (stream-cdr s) X))))
  X)

(define (div-series s1 s2)
  (if (= 0 (stream-car s2)) 'Error
      (mul-series s1 (invert-unit-series s2))))

(define cosine-series
  (cons-stream 1 (mul-stream minus-one (integrate-series sine-series))))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))

(define tangent-series (div-series sine-series cosine-series))


(newline)
(display (stream-ref tangent-series 0))(newline)
(display (stream-ref tangent-series 1))(newline)
(display (stream-ref tangent-series 2))(newline)
(display (stream-ref tangent-series 3))(newline)
(display (stream-ref tangent-series 4))(newline)
(display (stream-ref tangent-series 5))(newline)
(display (stream-ref tangent-series 6))(newline)
(display (stream-ref tangent-series 7))(newline)
(display (stream-ref tangent-series 8))(newline)
(display (stream-ref tangent-series 9))(newline)
(display (stream-ref tangent-series 10))(newline)
(display (stream-ref tangent-series 11))(newline)

;; Output
;Loading "sicp_prob_03.62.scm"...
;0
;1
;0
;1/3
;0
;2/15
;0
;17/315
;0
;62/2835
;0
;1382/155925
;... done



sicp exercise 3.61



;;Exercise 3.61.  Let S be a power series (exercise 3.59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S · X = 1. Write S = 1 + SR where SR is the part of S after the constant term. Then we can solve for X as follows:



;;In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of SR times X. Use this idea to write a procedure invert-unit-series that computes 1/S for a power series S with constant term 1. You will need to use mul-series from exercise 3.60.


(define (integrate-series s)
  (define (integrate-series-i s n)
    (cons-stream  (/ (stream-car s) n)
                  (integrate-series-i (stream-cdr s) (+ 1 n))))
  (integrate-series-i s 1))

(define (mul-stream s1 s2)
  (stream-map * s1 s2))

(define minus-one
  (cons-stream -1 minus-one))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (add-streams s1 s2)
  (cons-stream (+ (stream-car s1) (stream-car s2))
               (add-streams (stream-cdr s1)(stream-cdr s2))))

(define (mul-series s1 s2)
  (cons-stream
    (* (stream-car s1)
       (stream-car s2))
    (add-streams
       (add-streams (scale-stream (stream-cdr s1) (stream-car s2))
                    (scale-stream (stream-cdr s2) (stream-car s1)))
       (cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2))))))

(define (invert-unit-series s)
  (define X
    (cons-stream 1 (mul-stream minus-one (mul-series (stream-cdr s) X))))
  X)

(define exp-series
  (cons-stream 1 (integrate-series exp-series)))

(define inverse-exp-series (invert-unit-series exp-series))

;; Testing:
;; computing series expansion of 1/e^x. which is equal to e^-x
;; so the result should be same as e^x but with alternate signs
(newline)
(display (stream-ref inverse-exp-series 0))(newline)
(display (stream-ref inverse-exp-series 1))(newline)
(display (stream-ref inverse-exp-series 2))(newline)
(display (stream-ref inverse-exp-series 3))(newline)
(display (stream-ref inverse-exp-series 4))(newline)
(display (stream-ref inverse-exp-series 5))(newline)
(display (stream-ref inverse-exp-series 6))(newline)
(display (stream-ref inverse-exp-series 7))(newline)
(display (stream-ref inverse-exp-series 8))(newline)

;; Output:
;Loading "sicp_prob_03.61.scm"...
;1
;-1
;1/2
;-1/6
;1/24
;-1/120
;1/720
;-1/5040
;1/40320
;... done

; Indeed it is.....

Sunday, December 19, 2010

sicp exercise 3.60



;; Exercise 3.60.  With power series represented as streams of coefficients as in exercise 3.59, adding series is implemented by add-streams. Complete the definition of the following procedure for multiplying series:

;; (define (mul-series s1 s2)
;;  (cons-stream <??> (add-streams <??> <??>)))

;; You can test your procedure by verifying that sin^2 x + cos^2 x = 1, using the series from exercise 3.59.



(define (integrate-series s)
  (define (integrate-series-i s n)
    (cons-stream  (/ (stream-car s) n)
                  (integrate-series-i (stream-cdr s) (+ 1 n))))
  (integrate-series-i s 1))

(define (mul-stream s1 s2)
  (stream-map * s1 s2))

(define minus-one
  (cons-stream -1 minus-one))


(define cosine-series
  (cons-stream 1 (mul-stream minus-one (integrate-series sine-series))))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (add-streams s1 s2)
  (cons-stream (+ (stream-car s1) (stream-car s2))
               (add-streams (stream-cdr s1)(stream-cdr s2))))

(define (mul-series s1 s2)
  (cons-stream
    (* (stream-car s1)
       (stream-car s2))
    (add-streams
       (add-streams (scale-stream (stream-cdr s1) (stream-car s2))
                    (scale-stream (stream-cdr s2) (stream-car s1)))
       (cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2))))))

(define test (add-streams (mul-series sine-series sine-series)
                          (mul-series cosine-series cosine-series)))

(newline)
(display (stream-ref test 0))(newline)
(display (stream-ref test 1))(newline)
(display (stream-ref test 2))(newline)
(display (stream-ref test 3))(newline)
(display (stream-ref test 4))(newline)
(display (stream-ref test 5))(newline)

;;Output:
;Loading "sicp_prob_03.60.scm"...
;1
;0
;0
;0
;0
;0
;... done

sicp exercise 3.59



;; Exercise 3.59.  In section 2.5.3 we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with power series, such as
;;



;;
;; represented as infinite streams. We will represent the series a0 + a1 x + a2 x2 + a3 x3 + ·Â·Ã‚· as the stream whose elements are the coefficients a0, a1, a2, a3, ....
;;
;; a. The integral of the series a0 + a1 x + a2 x2 + a3 x3 + ·Â·Ã‚· is the series
;;

;;
;; where c is any constant. Define a procedure integrate-series that takes as input a stream a0, a1, a2, ... representing a power series and returns the stream a0, (1/2)a1, (1/3)a2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate-series, we will cons on the appropriate constant.)
;;
;; b. The function x->e^x is its own derivative. This implies that ex and the integral of ex are the same series, except for the constant term, which is e0 = 1. Accordingly, we can generate the series for ex as
;;
;; (define exp-series
;;   (cons-stream 1 (integrate-series exp-series)))
;;
;; Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:
;;
;; (define cosine-series
;;   (cons-stream 1 <??>))
;; (define sine-series
;;   (cons-stream 0 <??>))


(define (integrate-series s)
  (define (integrate-series-i s n)
    (cons-stream  (/ (stream-car s) n)
                  (integrate-series-i (stream-cdr s) (+ 1 n))))
  (integrate-series-i s 1))

(define (mul-stream s1 s2)
  (stream-map * s1 s2))

(define minus-one
  (cons-stream -1 minus-one))


(define cosine-series
  (cons-stream 1 (mul-stream minus-one (integrate-series sine-series))))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))


(newline)
(display (stream-ref sine-series 0))(newline)
(display (stream-ref sine-series 1))(newline)
(display (stream-ref sine-series 2))(newline)
(display (stream-ref sine-series 3))(newline)
(display (stream-ref sine-series 4))(newline)
(display (stream-ref sine-series 5))(newline)
(display (stream-ref sine-series 6))(newline)
(display (stream-ref sine-series 7))(newline)
(display (stream-ref sine-series 8))(newline)
(display "----------------------")(newline)
(display (stream-ref cosine-series 0))(newline)
(display (stream-ref cosine-series 1))(newline)
(display (stream-ref cosine-series 2))(newline)
(display (stream-ref cosine-series 3))(newline)
(display (stream-ref cosine-series 4))(newline)
(display (stream-ref cosine-series 5))(newline)
(display (stream-ref cosine-series 6))(newline)
(display (stream-ref cosine-series 7))(newline)
(display (stream-ref cosine-series 8))(newline)

;; Output:
;Loading "sicp_prob_03.59.scm"...
;0
;1
;0
;-1/6
;0
;1/120
;0
;-1/5040
;0
;----------------------
;1
;0
;-1/2
;0
;1/24
;0
;-1/720
;0
;1/40320
;... done



sicp exercise 3.58


;; Exercise 3.58.  Give an interpretation of the stream computed by the following procedure:
;;
;;(define (expand num den radix)
;;  (cons-stream
;;   (quotient (* num radix) den)
;;   (expand (remainder (* num radix) den) den radix)))
;;
;;(Quotient is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by (expand 1 7 10) ? What is produced by (expand 3 8 10) ?


(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))

(newline)
(display (stream-ref (expand 1 7 10) 0)) (newline)
(display (stream-ref (expand 1 7 10) 1)) (newline)
(display (stream-ref (expand 1 7 10) 2)) (newline)
(display (stream-ref (expand 1 7 10) 3)) (newline)
(display (stream-ref (expand 1 7 10) 4)) (newline)
(display (stream-ref (expand 1 7 10) 5)) (newline)
(display (stream-ref (expand 1 7 10) 6)) (newline)
(display (stream-ref (expand 1 7 10) 7)) (newline)
(display (stream-ref (expand 1 7 10) 8)) (newline)

(newline)
(newline)
(newline)

(display (stream-ref (expand 3 8 10) 0)) (newline)
(display (stream-ref (expand 3 8 10) 1)) (newline)
(display (stream-ref (expand 3 8 10) 2)) (newline)
(display (stream-ref (expand 3 8 10) 3)) (newline)
(display (stream-ref (expand 3 8 10) 4)) (newline)
(display (stream-ref (expand 3 8 10) 5)) (newline)
(display (stream-ref (expand 3 8 10) 6)) (newline)
(display (stream-ref (expand 3 8 10) 7)) (newline)
(display (stream-ref (expand 3 8 10) 8)) (newline)

; Output:
;Loading "sicp_prob_03.58.scm"...
;1
;4
;2
;8
;5
;7
;1
;4
;2
;
;
;
;3
;7
;5
;0
;0
;0
;0
;0
;0
;... done


sicp exercise 3.57



;; Exercise 3.57.  How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay <exp>) simply as (lambda () <exp>), without using the optimization provided by the memo-proc procedure described in section 3.5.1

(define numofsum 0)
(define (plus a b)
  (set! numofsum (+ 1 numofsum))
  (+ a b))

(define (reset)(set! numofsum 0))

(define (add-streams s1 s2)
  (stream-map plus s1 s2))

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

(newline)
(display (stream-ref fibs 0))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 1))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 2))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 3))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 4))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 5))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 6))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 20))(display " ")(display numofsum)(newline)



(display "-------------")(newline)


(reset)
(define (fibo n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (plus (fibo (- n 1))
                 (fibo (- n 2))))))

(display (fibo 0)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 1)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 2)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 3)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 4)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 5)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 6)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 20)) (display " ") (display numofsum) (newline)(reset)

;; Output:
;Loading "sicp_prob_03.57.scm"...
;0 0
;1 0
;1 1
;2 2
;3 3
;5 4
;8 5
;6765 19
;-------------
;0 0
;1 0
;1 1
;2 2
;3 4
;5 7
;8 12
;6765 10945
;... done