Shane

Joined 2 years ago

Homeworks submitted:
Homework comments:

2
1

About Me

No description provided.

Classes

Structure and Interpretation of Computer Programs

Class status: Established
Role: Student

. 15% complete

Submitted Assignments

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

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)

As it maintains it's state through arguments only.

Exercise 1.10

1024

65536

f(n) = 2 * n g(n) = 2^n h(n) = 2^(h(n-1)) Where n > 1 Example: h(0) = 0 h(1) = 2^(0)) != 2 //Should be 1 h(2) = 2^(2) = 4 h(3) = 2^(4) = 16 h(4) = 2^(16) = 65536

Exercise 1.13 Could not solve but good solution here. http://www.billthelizard.com/2009/12/sicp-exercise-113-fibonacci-and-golden.html

Exercise 1.15 a. 5 times b. Appears to log O(log(a)) as doubling the input angle appears to increase the number of calls a constant amount. The space appears to also be O(log(a)) the angle is roughly halved through each recursive call.

Exercise 1.19 Could not solve.

Exercise 1.21 199 1999 7

Exercise 1.22 1009 1013 1019 10007 10009 10037 100003 100019 100043 1000003 1000033 1000037

Could not verify time, runtime did not work in DrScheme and the only thing that did, (current-inexact-milliseconds) displayed -0.0009765625 for every type of input.

Exercise 1.25 This can produce the same results. Though becomes incredibly slow on large numbers and isn't as suited as a fast prime tester. But I'm not entirely sure why.

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

(f 4)

(define (fi n)
  (iter-f 2 1 0 n))
 
(define (iter-f n nmo nmt ind)
  (cond ((< ind 3) n)
        (else (iter-f (+ n (* 2 nmo) (* 3 nmt)) n nmo (- ind 1))))
  )

(fi 4)

;State is held in args

Exercise 1.17
(define (fast-mul a b addr)  (cond ((= b 1) (+ a addr))
        ((= b -1) (+ a addr))
        ((even b) (fast-mul (double a) (half b) addr))
        (else (fast-mul a (- b 1) (+ addr a)))))

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

(define (double n)
  (* n 2))

(define (even n)
  (= (remainder n 2) 0))

(fast-mul 64 64 0)

Exercise 1.23
(define (square n)  (* n n))

(define (next n)
  (cond ((= n 2) 3)
        (else (+ n 2))))

Results were the same but again cannot verify time or difference.

Exercise 1.27
(define (square n)  (* n n))

(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 n)
  (define (try-it a)
    (= (expmod a n n) a))
  (define (fermat-iter a)
    (cond ((= a 0) #f)
          ((not (try-it a)) #t)
          (else (fermat-iter (- a 1)))))
  (fermat-iter (- n 1)))

(fermat-test 4)
(fermat-test 561)
(fermat-test 1105)
(fermat-test 1729)
(fermat-test 2465)
(fermat-test 6601)

Shane 2 years ago

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

Exercise 1.1 10 12 8 3 6 a b 19 false 4 16 6 16

Exercise 1.4 Adds absolute value of b to a. Based on if b is greater than 0 it will select which operator (+ or -) to apply to args a and b.

Exercise 1.5 (p) = (p) will infinitely evaluate the argument (p)

Exercise 1.6 Applicative order will cause the (sqrt-iter (improve guess x) to be infinitely called as it will constantly expand the arguments.

Exercise 1.7 For small numbers the check of difference 0.001 will produce rounding errors. For large number there isn't enough precision to stop the result.


Exercise 1.7
(define (square x)
  (* x x))

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

(define (squrt x)
  (define (good-enough? guess old_guess)
    (< (abs (- guess old_guess)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess old_guess)
    (if (good-enough? guess old_guess)
        guess
        (sqrt-iter (improve guess) guess)))
  (sqrt-iter 1.0 0.0))

(squrt 1094)

Exercise 1.8
(define (cube x)
  (* x x x))

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

(define (cube-root x)
  (define (good-enough? guess)
    (< (abs (- x (cube guess))) 0.001))
  (define (improve guess)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
  (define (cube-iter guess)
    (if (good-enough? guess)
        guess
        (cube-iter (improve guess))))
  (cube-iter 1.0))

(cube-root 1094)

Shane 2 years ago