Curious Reef: Exploratory social learning

Structure and Interpretation of Computer Programs: Lesson 4, HW 1

;Exercise 2.1
(define (make-rat x y)
  (let ((g (gcd x y)))
    (let ((numer (abs (/ x g)))
          (denom (abs (/ y g))))
      (cons (if (< (* x y) 0) 
                (- numer) 
                numer)
            denom))))
			  
			  
;Exercise 2.2
(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 s)
  (let ((x1 (x-point (start-segment s)))
        (y1 (y-point (start-segment s)))
        (x2 (x-point (end-segment s)))
        (y2 (y-point (end-segment s))))
    (make-point (avg x1 x2)
                (avg y1 y2))))

				
;Exercise 2.3
(define (area rect)
  (* (width rect)
     (height rect)))
(define (perim rect)
  (* 2 (+ (width rect)
          (height rect))))

;a segment representing the diagonal is used
(define (make-rectangle p1 p2) 
  (make-segment p1 p2))
(define (width rect)
  (abs (- (x-point (start-segment rect))
          (x-point (end-segment rect)))))
(define (height rect)
  (abs (- (y-point (start-segment rect))
          (y-point (end-segment rect)))))

;the upper-left and lower-right points are used here
(define (make-rectangle p1 p2)
  (cons p1 p2))
(define (width rect)
  (abs (- (x-point (car rect))
          (x-point (cdr rect)))))
(define (height rect)
  (abs (- (y-point (car rect))
          (y-point (cdr rect)))))

(define rect (make-rectangle (make-point 0 2) 
                             (make-point 4 0)))

(area rect)
(perim rect)


;Exercise 2.4
(define (cdr z)
  (z (lambda (p q) q)))

(cdr (cons 2 3))
(cdr (lambda (m) (m 2 3)))
(cdr (lambda (2 3) 3))
(3) ;it returned the second element  


;Exercise 2.5
(define (divide n by cnt)
  (if (= (remainder n by) 0)
      (divide (/ n by)
              by
              (+ cnt 1))
      cnt))

(define (cons a b)
  (* (exp-fast 2 a)
     (exp-fast 3 b)))

(define (car n)
  (divide n 2 0))

(define (cdr n)
  (divide n 3 0))
 
 
;Exercise 2.7
(define (make-interval a b) (cons a b))
(define (lower-bound iv) (car iv))
(define (upper-bound iv) (cdr iv))


;Exercise 2.8
(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))

				 
;Exercise 2.9
(define (width-interval x)
  (/ (- (upper-bound x) (lower-bound x)) 2.0))

(define iv1 (make-interval 2 3))
(define iv2 (make-interval 5 8))
(width-interval iv1)
(width-interval iv2)
(width-interval (add-interval iv1 iv2)) ;sum of widths iv1 and iv2
(width-interval (sub-interval iv1 iv2)) ;sum of widths iv1 and iv2
(width-interval (mul-interval iv1 iv2)) ;not a function
(width-interval (div-interval iv1 iv2)) ;not a function
				 
						 
;Exercise 2.10
(define (div-interval x y)
  (if (and (>= (upper-bound y) 0) (<= (lower-bound y) 0))
      (error "Cannot divide by an interval that spans zero")
      (mul-interval x 
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))						   
				 
;Exercise 2.11
(define (mul-interval x y)
  (define x-sign (cond ((and (< (lower-bound x) 0) (< (upper-bound x) 0)) (- 1))
                       ((and (< (lower-bound x) 0) (> (upper-bound x) 0)) 0)
                       ((and (> (lower-bound x) 0) (> (upper-bound x) 0)) 1)))
  (define y-sign (cond ((and (< (lower-bound y) 0) (< (upper-bound y) 0)) (- 1))
                       ((and (< (lower-bound y) 0) (> (upper-bound y) 0)) 0)
                       ((and (> (lower-bound y) 0) (> (upper-bound y) 0)) 1)))
  (cond ((< x-sign 0)
         (cond ((< y-sign 0) (make-interval (* (upper-bound x) (upper-bound y))
                                            (* (lower-bound x) (lower-bound y))))
               ((= y-sign 0) (make-interval (* (lower-bound x) (upper-bound y))
                                            (* (lower-bound x) (lower-bound y))))
               (else (make-interval (* (lower-bound x) (upper-bound y))
                                    (* (upper-bound x) (lower-bound y))))))
        ((= x-sign 0)
         (cond ((< y-sign 0) (make-interval (* (upper-bound x) (lower-bound y))
                                            (* (lower-bound x) (lower-bound y))))
               ((= y-sign 0) (make-interval ((min (* (upper-bound x) (lower-bound y))
                                                  (* (lower-bound x) (upper-bound y)))
                                             (max (* (upper-bound x) (upper-bound y))
                                                  (* (lower-bound x) (lower-bound y))))))
               (else (make-interval (* (lower-bound x) (upper-bound y))
                                    (* (upper-bound x) (upper-bound y))))))
        (else 
         (cond ((< y-sign 0) (make-interval (* (upper-bound x) (lower-bound y))
                                            (* (lower-bound x) (upper-bound y))))
               ((= y-sign 0) (make-interval (* (upper-bound x) (lower-bound y))
                                            (* (upper-bound x) (upper-bound y))))
               (else (make-interval (* (lower-bound x) (lower-bound y))
                                    (* (upper-bound x) (upper-bound y))))))))

									
;Exercise 2.12
(define (make-center-percent c p)
  (define width (* (/ p 100.0) c))
  (make-interval (- c width)
                 (+ c width)))

(define (center i)
  (/ (+ (upper-bound i) (lower-bound i)) 2.0))

(define (percent i)
 (* (/ (lower-bound i) (center i)) 100))

thejasper 1 year ago

Structure and Interpretation of Computer Programs: Lesson 3, HW 1

;Exercise 1.29
;The procedure based on Simpsons's Rule gives as said better results
(define (integral f a b n)
  (define h (/ (- b a) n))
  (define (y k) (+ a (* k h)))
  (define (term k)
    (if (= (remainder k 2) 0)
        (* 2.0 (f (y k)))
        (* 4.0 (f (y k)))))
  (define (inc x) (+ x 1))
  (* (/ h 3) (+ (f (y 0))
                (sum term 1 inc (- n 1))
                (f (y n)))))
(integral cube 0 1 100)
0.24999999999999992
(integral cube 0 1 1000)
0.2500000000000002


;Exercise 1.30
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))

  
;Exercise 1.31
;Recursive process
(define (product factor a next b)
  (if (> a b)
      1
      (* (factor a)
         (product factor (next a) next b))))

;Iterative process
(define (product2 factor a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (factor a)))))
  (iter a 1))

(define (factorial n)
  (define (self x) x)
  (define (inc x) (+ x 1))
  (product2 self 1 inc n))

(define (pi-prod n)
  (define (sq x) (* x x))
  (define (next x) (+ x 2))
  (define last (* 2 n))
  (* 4 ( / ( / (product2 sq 2 next last) 2.0 last)
           (product2 sq 3 next last))))

(factorial 10)
3628800
(pi-prod 50)
3.157339689217565

;Exercise 1.35
(define golden-ratio (fixed-point 
                      (lambda (x) (+ 1.0 (/ 1.0 x))) 
                      1.0))
golden-ratio
1.6180327868852458		


;Exercise 1.37
;k must be 11 to get an approximation that is accurate to 4 decimal places
(define (cont-frac n d k)
  (define (helper i)
    (if (= i k)
        (/ (n i) (d i))
        (/ (n i) (+ (d i)
                    (helper (+ i 1))))))
  (helper 1))

;Iterative process
;it computes the fraction bottom-up, starting with Nk/Dk
(define (cont-frac1 n d k)
  (define (helper i result)
    (if (= i 1)
        (/ (n 1) (+ (d 1) result))
        (helper (- i 1) (/ (n i) (+ (d i) result)))))
  (helper k 0))
  

;Exercise 1.39
(define (tan-cf x k)
  (cont-frac (lambda (i) (if (= i 1)
                              x
                              (- (square x))))
              (lambda (i) (+ 1 (* 2 (- i 1))))
              k))

 
;Exercise 1.41
(define (double f)
  (lambda (x) (f (f x))))
  
  
;Exercise 1.42
(define (compose f g)
  (lambda (x) (f (g x))))
  
  
;Exercise 1.43
(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

thejasper 1 year ago

Structure and Interpretation of Computer Programs: Lesson 2, HW 1

Exercise 1.9. The first one is a lineair recursive process and the second one is a lineair iterative process.

Exercise 1.10. (A 1 10) = 1024 (A 2 4) = 65536 (A 3 3) = 65536 (f n) computes 2n (g n) computes 2^n (h n) computes 2^h(n-1)

Exercise 1.14. Draw the tree. Done. 12 ways to return the money. The space and time complexity are O(amount * num-coins).

Exercise 1.15. When sine is called, the angle is divided by 3. When the angle is smaller than 0.1 the procedure stops calling himself. 12.15 / 3^5 = 0.05 so the answer is 5 times. angle/3^n=0.1 => Space and time complexity are O(log(angle))

Exercise 1.20. When a normal-order evaluation is used, remainder is evaluated 18 times. With application-order evaluation only 4 times.

Exercise 1.21. 199, 1999 and 7. This means that the first 2 are prime.

*Exercise 1.22. I used a bit larger numbers so the timing data would make more sense. I used the average of the timings of the first 3 prime numbers.

10^10 : 120ms

10^11 : 406ms -> ratio with previous: 3.37

10^12 : 1346ms -> 3.32

10^13 : 4212ms -> 3.13

sqrt(10) = 3.16 so the run time is proportional to the number of steps required for the computation.

Exercise 1.23. Timings with the modified version of smallest-divisor, again with averages:

10^10 : 63ms -> old/new: 1.90

10^11 : 239ms -> 1.70

10^12 : 707ms -> 1.90

10^13 : 2267ms -> 1.85

The new version almost runs twice as fast. Maybe because there are some constants that are not affected by the change we made. Also the new procedure creates some overhead.

Exercise 1.24. I chose to let the fast-prime? procedure test 500 times. For small values the ratio was pretty poor compared to the other prime test. But the timing increased slow when the range increased. The procedure is logarithmic due to the expmod procedure.

Exercise 1.25. The procedure is correct but it will not be as efficient because there will be larger intermediate values. So it will take longer to compute for example the product.

Exercise 1.26. If expmod is implemented like this, then it's tree recursion.

;Exercise 1.9.
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

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

;Exercise 1.11
;recursive version
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

;iterative version
(define (f n)
  (f-iter 0 0 1 2 n))
(define (f-iter cnt a b c max)
  (if (= cnt max)
      a
      (f-iter (+ cnt 1)
              b
              c
              (+ c
                 (* 2 b)
                 (* 3 a))
              max)))

;Exercise 1.12
;row and col start from zero
(define (triangle row col)
  (if (or (= row col) (= col 0))
      1
      (+ (triangle (- row 1)
                   (- col 1))
         (triangle (- row 1)
                   col))))
				   
;Exercise 1.16
(define (exp b n)
  (exp-iter b n 1))
(define (exp-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (exp-iter (square b) 
                             (/ n 2) 
                             a))
        (else (exp-iter b 
                        (- n 1) 
                        (* a b)))))

;Exercise 1.17
(define (multiply x y)
  (cond ((= y 0) 0)
        ((even? y) (multiply (double x) (halve y)))
        (else (+ x (multiply x (- y 1))))))
		
;Exercise 1.18
(define (multiply x y)
  (mul-iter x y 0))
(define (mul-iter x y a)
  (cond ((= y 0) a)
        ((even? y) (mul-iter (double x) (halve y) a))
        (else (mul-iter x (- y 1) (+ a x)))))
		
;Exercise 1.22
;low gives the lower bound and cnt says how much prime numbers it has to output
(define (search-for-primes low cnt)
  (cond ((even? low) (search-for-primes (+ low 1) cnt))
        ((> cnt 0)
         (cond ((prime? low)
                (timed-prime-test low) ;it's computed twice..
                (search-for-primes (+ low 2) (- cnt 1)))
               (else
                (search-for-primes (+ low 2) cnt))))))
				
;Exercise 1.23
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))
(define (divisor n div)
  (cond ((> (square div) n) n)
        ((divides n div) div)
        (else (divisor n (next div)))))
		
;Exercise 1.27
;every carmichael number passes the test
(define (fool carmichael)
  (test 0 carmichael))
(define (test a n)
  (cond ((= a n) #t)
        ((= (expmod a n n) a) (test (+ a 1) n))
        (else #f)))

thejasper 1 year ago

Structure and Interpretation of Computer Programs: Lesson 1, HW 1

Exercise 1.1. 10 12 8 3 6 no output no output 19 false 4 16 6 16

Exercise 1.2. (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))(* 3 (- 6 2)(- 2 7)))

Exercise 1.4. If b is greater than zero -> a and b will be added. If b is zero or less -> b will be substracted from a. Because b is negative the two minus signs will cancel eachother out. Therefore the procedure adds the absolute value of b to a.

Exercise 1.5. If Ben uses a interpreter that uses applicative-order evaluation the program will hang because it will try to evaluate and apply the arguments. Normal order evaluation will try to expand the expression without touching the arguments. Because x=0 the 'fatal' argument will never be evaluated.

Exercise 1.6. If the interpreter uses applicative-order evaluation the program will not finish. Both arguments of the new-if procedure will be evaluated. The second one is a recursive call so this will happen over and over again.

Exercise 1.7 If you choose a tolerance like 0.001. For small numbers it would be too big. For big numbers it would be too small. Another way of implementing good-enough would be to check the ratio between the old and the new guess. A small change results in a ratio close to 1. This is a better way to do this because it's independent of the size of the number.

;Exercise 1.3.
(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (sum x y z)
  (cond ((and (> x z) (> y z))(sum-of-squares x y))
        ((and (> x y) (> z y))(sum-of-squares x z))
        (else (sum-of-squares y z))))

;Exercise 1.7.
;the new good-enough
(define (good-enough? guess old)
    (< (abs (- (/ guess old) 1.0)) 0.001))
	
;Exercise 1.8.
(define (sqrt x)
  (define (abs x) (if (< x 0) (- x) x))
  (define (sqrt-iter guess old)
    (if (good-enough? guess old)
        guess
        (sqrt-iter (improve guess) guess)))
  (define (good-enough? guess old)
    (< (abs (- (/ guess old) 1.0)) 0.001))
  (define (improve guess) ;modified, gives a better guess for cube roots
    (/ (+ (/ x (* guess guess))(* 2 guess)) 3))
  (sqrt-iter 1.0 2.0))

thejasper 1 year ago

thejasper

About Me

Classes

Structure and Interpretation of Computer Programs

Submitted Assignments