Curious Reef: Exploratory social learning

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

I'm not sure about 2.14 and 2.15

; 2.13 ?

; 2.15 The percision is affected by the number of multiplications and divisions there are, so limiting these will give the least amount of error. So par1 would be best.

; 2.16 Hmm, maybe avoid multiplications/divisions until we can simplify or standardize the equation? There will still be rounding errors, but they could be consitant. I'm not sure how fesible this is. I imagine standardizing all equations would be difficult.

;2.1
(define (make-rat n d) 
  (let ((g (gcd n d)))
    (if (> 0 (* n d))
        (cons (/ (* -1 (abs n)) g) (/ (abs d) g))
        (cons (/ (abs n) g) (/ (abs d) g)))))
        
;2.2
(define (make-rat n d) 
  (let ((g (gcd n d)))
    (if (> 0 (* n d))
        (cons (/ (* -1 (abs n)) g) (/ (abs d) g))
        (cons (/ (abs n) g) (/ (abs d) g)))))

(define (numer x) (car x)) 
(define (denom x) (cdr x))

;Point
(define (make-point x-point y-point)
  (cons x-point y-point))
(define (x-point point) (car point))
(define (y-point point) (cdr point))

(define (print-point p) 
  (newline) 
  (display "(") 
  (display (x-point p)) 
  (display ",") 
  (display (y-point p)) 
  (display ")"))

;Line
(define (make-line start-point end-point)
  (cons start-point end-point))
(define (start-point line) (car line))
(define (end-point line) (cdr line))

; midpoint
(define (midpoint line)
  (define (avg x y) (/ (+ x y) 2.0))
  (make-point (avg (x-point (start-point line)) (x-point (end-point line)))
              (avg (y-point (start-point line)) (y-point (end-point line)))))

(print-point (midpoint (make-line (make-point 0 0) (make-point 0 6))))
(print-point (midpoint (make-line (make-point 5 89) (make-point 7 83))))

; Output
; (0,3.0)
; (6.0,86.0)

;2.3
; RectangleA
(define (make-rectA height length)
  (cons height length))
(define (height rectA) (car rectA))
(define (length2 rectA) (cdr rectA))
(define (perimeter rectA)
        (+ (* 2 (height rectA))
           (* 2 (length2 rectA))))
(define (area2 rectA)
        (* (height rectA)
           (length2 rectA)))

(define rectA (make-rectA 5 5))
(perimeter rectA)
(area2 rectA)

; RectangleB
; define length for line
(define (line-length line) 
  (sqrt (+
         (square (abs (- 
                       (x-point (start-point line)) 
                       (x-point (end-point line)))))
         (square (abs (- 
                       (y-point (start-point line)) 
                       (y-point (end-point line))))))))

(define (make-rectB lineHeight lineWidth)
  (cons lineHeight lineWidth))
(define (heightB rectB) (line-length (car rectB)))
(define (widthB rectB) (line-length (cdr rectB)))

(define (perimeterB rectB)
        (+ (* 2 (heightB rectB))
           (* 2 (widthB rectB))))
(define (areaB rectB)
        (* (heightB rectB)
           (widthB rectB)))

(define rectB (make-rectB
               (make-line (make-point 0 0) (make-point 0 5))
               (make-line (make-point 0 5) (make-point 5 5))))
               
(perimeterB rectB)
(areaB rectB)

;2.4
(define (cdr2 z)
  (z (lambda (p q) q)))
  
;2.5
(define (multiple-of-3 n) (= (remainder n 3) 0))

(define (cons a b) (* (expt 2 a) (expt 3 b)))

; Divide by two until we can't
(define (car x)
  (define (iter x count)
    (if (not (even? x))
        count
        (iter (/ x 2) (+ count 1))))
  (iter x 0))

; Divide by 3 until we can't
(define (cdr x)  
  (define (iter x count)
    (if (not (multiple-of-3 x))
        count
        (iter (/ x 3) (+ count 1))))
  (iter x 0))


;2.6
(define (one) (lambda (x) (f (((lamda (f) (lambda (x) x)) f) x))))

(define (two) (lambda (f) lambda (x) (f (((lambda (x) (f (((lamda (f) (lambda (x) x)) f) x))) f) x ))))

;2.7
(define (make-interval a b) (cons a b))
(define (lower-bound interval)
  (if (< (car interval) (cdr interval))
      (car interval)
      (cdr interval)))
(define (upper-bound interval)
  (if (< (car interval) (cdr interval))
      (cdr interval)
      (car interval)))

;2.8
(define (sub-interval x y)
  (let ((p1 (- (lower-bound x) (lower-bound y))) 
        (p2 (- (lower-bound x) (upper-bound y)))
        (p3 (- (upper-bound x) (lower-bound y)))
        (p4 (- (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4))))
    
;2.9
interval 1= a to b
width 1 = (b-a)/2
interval 2 = c to d
width 2 - (d-c)/2

int1 + int2
(a + c) to (b + d)
the width would be
((b +d) - (a + c))/2
(b/2 + d/2 - a/2 + c/2)
(b-a)/2 + (d-c)/2
width1 + width2

int1 = -1 to 1 width 1
int2 = 1 to 2 width .5
int1*int2
-2 to 2
width 2

and

int1 = 1 to 2 width .5
int2 = 1 to 2 width .5
int1*int2 = 1 to 4 
width=2 again, despite starting with diffrent widths.

;2.10
(define (interval-span-0? interval)
  (and (> 0 (lower-bound interval)) (< 0 (upper-bound interval))))
(define (div-interval x y)
  (if (or (interval-span-0? x) (interval-span-0? y))
      (display "Can not divide when a inverval spans 0")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))                   
                                   (/ 1.0 (lower-bound y))))))

;2.11
a b c d
+ + + + (ac) (bd) 
+ + - + (bc) (bd)
+ + - - (bc) (ad)
- + + + (ad) (bd) 
- + - + (bc) (bd) or (bc) (ac)
- + - - (bc) (ac)
- - + + (ad) (bc)
- - - + (bd) (ac)
- - - - (bd) (ac)

;2.11
(define (lower-neg x)
  (> 0 (lower-bound x)))
(define (lower-pos x)
  (< 0 (lower-bound x)))
(define (upper-neg x)
  (> 0 (upper-bound x)))
(define (upper-pos x)
  (< 0 (upper-bound x)))

(define (mul-interval2 x y)
  (cond 
    ; + + + + ac bd
    ((and (lower-pos x) (upper-pos x) (lower-pos y) (upper-pos y)
         (make-interval (* (lower-bound x) (lower-bound y)) 
                        (* (upper-bound x) (upper-bound y)))))
        
    ; + + - + bc bd    
    ((and (lower-pos x) (upper-pos x) (lower-neg y) (upper-pos y)
         (make-interval (* (upper-bound x) (lower-bound y)) 
                        (* (upper-bound x) (upper-bound y)))))
    
    ; + + - - bc ad  
    ((and (lower-pos x) (upper-pos x) (lower-neg y) (upper-neg y)
         (make-interval (* (upper-bound x) (lower-bound y)) 
                        (* (lower-bound x) (upper-bound y)))))
    
    ; - + + + ad bd  
    ((and (lower-neg x) (upper-pos x) (lower-pos y) (upper-pos y)
         (make-interval (* (lower-bound x) (upper-bound y)) 
                        (* (upper-bound x) (upper-bound y)))))

    ; - + - + bc bd OR bc ac  
    ((and (lower-neg x) (upper-pos x) (lower-pos y) (upper-pos y)
          (let ((p1 (* (lower-bound x) (lower-bound y))) 
                (p2 (* (lower-bound x) (upper-bound y)))
                (p3 (* (upper-bound x) (lower-bound y)))
                (p4 (* (upper-bound x) (upper-bound y))))
            (make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4)))))
    
    ; - + - - bc ac  
    ((and (lower-neg x) (upper-pos x) (lower-neg y) (upper-neg y)
         (make-interval (* (upper-bound x) (lower-bound y)) 
                        (* (lower-bound x) (lower-bound y)))))    
    
    ; - - + + ad bc  
    ((and (lower-neg x) (upper-neg x) (lower-pos y) (upper-pos y)
         (make-interval (* (lower-bound x) (upper-bound y)) 
                        (* (upper-bound x) (lower-bound y)))))     
    
    ; - - - + bd ac
    ((and (lower-neg x) (upper-neg x) (lower-neg y) (upper-pos y)
         (make-interval (* (upper-bound x) (upper-bound y)) 
                        (* (lower-bound x) (lower-bound y))))) 
    
    ; - - - - bd ac
    ((and (lower-neg x) (upper-neg x) (lower-neg y) (upper-neg y)
         (make-interval (* (upper-bound x) (upper-bound y)) 
                        (* (lower-bound x) (lower-bound y))))))) 

;2.12
(define (make-center-percentage c p)
  (make-center-width c (abs (* c p)))

(define (percentage interval)
  (/ (center interval) (width interval)))
  
; 2.13
(define a (make-center-percentage .25 .01))
(define b (make-center-percentage .10 .01))

(par1 a b)
(par2 a b)

> (0.0693140028288543 . 0.0736002886002886)
> (0.07071428571428572 . 0.07214285714285715)

dtmetz 2 years ago

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

;A little late, but here is what I got.  
;I'm not sure what is wrong with my tan function though:

;1.3 Homework
;Problems: 1.29, 1.30, 1.31, 1.35, 1.39, 1.41, 1.42, 1.43

;1.29
(define (simposon-integral2 f a b n)
  (define h 
    (/ (- b a) n))
  (define (next x) (+ x (* 2 h)))
  
  (* (/ h 3.0) (+ (f a)
                  (f b)
                  (* 4 (sum f (+ a h) next (- b h)))
                  (* 2 (sum f (+ a (* h 2)) next (- b (* h 2)))))))
                  
(simposon-integral2 cube 0 1 100)
(simposon-integral2 cube 0 1 1000)

0.25
0.25

;1.30
(define (sum term a next b) 
  (define (iter a result)
    (if (> a b) 
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))
  
;1.31
(define (product-rec term a next b) 

  (if (> a b) 
      1
      (* (term a) 
         (product-rec term (next a) next b))))

(define (prodcut-iter term a next b) 
  (define (iter a result)
    (if (> a b) 
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

; Factorial 1 to 10
(define (nothing x) (+ x 0))
(define (inc x) (+ x 1))
(product-rec nothing 1 inc 10)
(prodcut-iter nothing 1 inc 10)

; pi/4
(define (piBy4 n)
  (define (nextPi x) (+ x 2))
  (define (square x) (* x x))
  ;((product-rec square 3 nextPi (- n 1)))))

  ;(product-rec square 4 nextPi n))
  ;(* 2 (product-rec square 4 nextPi (- n 2)) n))
  (/ (* 2 (product-rec square 4.0 nextPi (- n 2)) n)
     (product-rec square 3.0 nextPi (- n 1))))

(piBy4 50)

> 3628800
> 3628800
> 0.7932910175598827

;1.35
; x^2 = X + 1
; x = 1 + 1/x
(define tolerance 0.00001) 
  (define (fixed-point f first-guess)
    (define (close-enough? v1 v2) 
      (< (abs (- v1 v2)) tolerance))
    (define (try guess) 
      (let ((next (f guess)))
        (if (close-enough? guess next) 
            next
            (try next))))
    (try first-guess))
  
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

> 1.6180327868852458

;1.39
(define (cont-frac N D k)
  (define (iter count currentValue)
    (if (= 1 count)
        (/ (N 1) currentValue)
        (iter (- count 1) 
              (+ (D (- count 1)) (/ (N count) currentValue)))))    
  (iter k (/ (N k) (D k))))

(define (tan-cf x k)
  (define (xsqaured k)
    (if (= k 1.0)
        x    
        (* x x)))
  (cont-frac xsqaured (lambda (i) (+ 1 (* (- i 1) 2.0))) k))

(tan 1.0)
(tan-cf 3.14 10000) 

(define (test k)
  (+ 1 (* (- k 1) 2.0)))
  
> 1.5574077
> 0.9962602
; Something isn't right here....

;1.41
(define (inc x)
  (+ x 1))

(define (double f)
  (lambda (x) (f (f x))))

(((double (double double)) inc) 5)
> 21

;1.42
(define (square x) (* x x))
(define (inc x) (+ x 1))

(define (compose f g)
  (lambda (i) (f (g i))))

((compose square inc) 6)

> 49

;1.43
(define (square x) 
  (* x x))

(define (repeated f n)
  (define (repeated-rec count)
    (if (= n count)
        (lambda (i) (f i))
        (lambda (i) (f ((repeated-rec (+ count 1)) i)))))
        
    (repeated-rec 1))
  

((repeated square 2) 5)

> 625

dtmetz 2 years ago

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

1.13 Couldn't figure this out - wikipedia has a proof, but I don't fully follow.

1.15 a) sin 12.15 12.15/3 = 4.05/3 = 1.35/3 = 0.45/3 = .15/3 = 0.05 1+ 2+ 3+ 4+ 5 = 5 times

b) O(log(n)) - growth O(log(n)) - steps We are dividing the angle in half each time iteration

1.21 199 1999 7

1.25 Yes, this would work. In expmod we checking the same conditions, then calling remainder on it.

This is better too, because if we had a faster way of calculating the exponent of a number we could just plug in another version with out touching expmod.

;1.9
(+ 4 5)
((inc (+ (4-1) 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
This is recursive

and

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

; 1.11
; Recursive
(define (f n)
  (cond ((< n 3) 3)
        (else (+ (f (- n 1)) 
                 (* 2 (f (- n 2))) 
                 (* 3 (f (- n 3)))))))


; Iterative
(define (f2 n)
  (f-iter 3 3 3 n))

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


1.17
(define (double n) 
  (+ n n))

(define (half n) 
  (/ n 2))

(define (even2? n) 
  (= (remainder n 2) 0))

(define (fast* a b)
  (cond ((= a 0) 0)
        ((= b 0) 0)
        ((even2? b) (fast* (double a) (half b)))
        (else (+ a (fast* a (- b 1))))))

1.19
(define (fib n) 
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count) 
  (cond ((= count 0) b)
        ((even? count) 
         (fib-iter a
                   b
                   (+ (* p p) (* q q ))  ; compute p'
                   (+ (* 2 p q) (* q q)) ; compute q'
                   (/ count 2))) 
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q)) 
                        p
                        q
                        (- count 1)))))

1.27
(define (expmod base exp m) 
  (cond ((= exp 0) 1)
        ((even? exp) 
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test-all n)
  (define (try-it a)
    (not (= (expmod a n n) a)))
  
  (define (fermat-iter n count)
    (cond ((= n count) (= 1 0))
          ((try-it count) (= 1 1))
          (else (fermat-iter n (+ count 1)))))
  
  (fermat-iter n 2))
  
; Returns true if any numbers satisfy Fermat's Test
; Sanity Check
(display "150 ")
(fermat-test-all 150)

; Carmichael numbers
(display "561 " )
(fermat-test-all 561)

(display "1105 ")
(fermat-test-all 1105)

(display "1729 ")
(fermat-test-all 1729)

(display "2465 ")
(fermat-test-all 2465)

(display "6601 ")
(fermat-test-all 6601)

Output:
150 #t
561 #f
1105 #f
1729 #f
2465 #f
6601 #f

dtmetz 2 years ago

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

1.1 10 ;Value: 10 (+ 5 3 4) ;Value: 12 (- 9 1) ;Value: 8 (/ 6 2) ;Value: 3 (+ ( 2 4) (- 4 6)) ;Value: 6 (define a 3) ;Value: a (define b (+ a 1)) ;Value: b (+ a b ( a b)) ;Value: 19 (= a b) ;Value: #f (if (and (> b a) ( b a) b a)) ;Value: 6 (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) ;Value: 16

1.4 The operator can change depending on if b is less then or greater then 0. If greater then, it adds a to b. If less then zero it subtracts b from a, giving us a + |b|.

1.5 Normal Order will cause and infinite recursive loop, where applicative-order will return 0. The reason is because p is a recursive call to itself. So if we try and fully expand (test 0 (p)) we will never finish because (p) will always be expanded into (p). However, if we are in applicative-order, then (= x 0) is evaluated first and the if statment can be checked without trying to expand (p).

This appears to be completely wrong upon testing :(

Hmm, I'll try and think about this more tomorrow...

1.6 Both of the parameters in her new-if method will be expanded, this causes a problem with recessive calls, if is special because the else doesn't need to be exceeded unless the first condition fails.

1.7 This test is not very good for small numbers because say the sort of .00000001 is .0001, so the check will stop as soon as it get's below .001.

For very large numbers there will be limit to the precision that a number can be expressed in. If the number is too large it will not expressed down to .001, so the calcuation will never be "good enough"

A better example wold be something like this to to normalize the comparison before checking how close it is. (define (good-enough2? guess x) (< (abs (/ (- (square guess) x) 2) 0.001))

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

1.3
(define (f a b c) 
  (cond ((and (< a b) (< a c))
         (+ (* b b) (* c c)))
        ((and (< b a) (< b c))
         (+ (* a a) (* c c)))
        (else
         (+ (* a a) (* b b)))))       
  
1.8
(define (cubert x)
  (cubert-iter 1.0 x))

(define (cubert-iter guess x)
  (if (good-enough3? guess x)
      guess
      (cubert-iter (improve guess x)
                 x)))

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))


(define (good-enough3? guess x)
  (< (abs (- (cube guess) x)) 0.001))

(define (cube x) 
  (* x x x))

(define (square x) 
  (* x x))

dtmetz 2 years ago

dtmetz

About Me

Classes

Structure and Interpretation of Computer Programs

Submitted Assignments