Learn faster and stay on-track by joining this free class with other self-learners.
Register for Structure and Interpretation of Computer Programs now.
|
Structure and Interpretation of Computer ProgramsClass length: 13 weeks. Start anytime. Creator: kday Status: Established |
Join this class! |
|
Lesson 1: Assignment 1Exercises in Section 1.1:Do exercises 1.1 through 1.8 in section 1.1. Homework Submissions28 total
1.1 10, 12, 8, 3, 6, no output, no output, 19, false, 4, 16, 6, 16 1.4 if b is positive add a and b. if b is negative subtract b from a. 1.5 applicative order will result in an infinite loop; normal-order will result in 0. 1.6 applicative-order would result in an infinite loop. 1.2 (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))(* 3 (- 6 2)(- 2 7)))
1.3
(define (square x) (* x x))
(define (square y) (* y y))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(define (f a b c)
(cond ((and (or (>= a b) (>= a c)) (or (>= b c) (>= b a))) (sum-of-squares a b))
((and (or (>= b a) (>= b c)) (or (>= c a) (>= c b))) (sum-of-squares b c))
((and (or (>= a b) (>= a c)) (or (>= c a) (>= c b))) (sum-of-squares a c))))
1.7
(define (sqrt-iter guess prev x)
(if (good-enough? guess prev)
guess
(sqrt-iter (improve guess x)
guess
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess prev)
(<
(abs (- 1 (/ guess prev)))
0.001))
(define (sqroot x)
(sqrt-iter 1.0 -1.0 x))
(define (square x)
(* x x))
1.8
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (good-enough? guess prev)
(<
(abs (- 1 (/ guess prev)))
0.001))
(define (cuberoot x)
(cube-rootiter 1.0 -1.0 x))
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))
No comments. Sign up or log in to comment 
Exercise 1.4If Exercise 1.5In an applicative-order interpreter, it will return the value Exercise 1.6
; Exercise 1.1
10
12
8
3
6
a
b
19
#f
4
16
6
16
; Exercise 1.2
(/
(+ 5 4
(- 2
(- 3
(+ 6
(/ 4 5)))))
(* 3
(- 6 2)
(- 2 7)))
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
; Exercise 1.3
(define (sum-of-squares a b c)
(define smallest
(cond ((and (< a b) (< a c)) a)
((and (< b a) (< b c)) b)
(else c)))
(cond ((= smallest a) (+ (* b b) (* c c)))
((= smallest b) (+ (* a a) (* c c)))
(else (+ (* a a) (* b b)))))
; Exercise 1.7
(define (good-enough? guess x last-guess)
(< (abs (- guess last-guess)) 0.0000000000001))
(define (sqrt-iter guess x last-guess)
(if (good-enough? guess x last-guess)
guess
(sqrt-iter (improve guess x)
x guess)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (sqrt x)
(sqrt-iter 1.0 x 10.0))
; Exercise 1.8
(define (cubert-iter guess x last-guess)
(if (good-enough? guess x last-guess)
guess
(cubert-iter (improve-cube guess x)
x guess)))
(define (improve-cube guess x)
(/
(+
(/ x (square guess))
(* 2 guess))
3))
(define (cubert x)
(cubert-iter 1.0 x 10.0))
No comments. Sign up or log in to comment 
;;; Ex 1.1
;;;
10
; 10
(+ 5 3 4)
; 12
(- 9 1)
; 8
(/ 6 2)
; 3
(+ (* 2 4) (- 4 6))
; 6
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
; 19
(= a b)
; #f
(if (and (> b a) (< b (* a b)))
b
a)
; 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
; 16
(+ 2 (if (> b a) b a))
; 6
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
; 16
;;; Ex 1.2
;;;
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))
;;; Ex 1.3
;;;
(define (sum-larger-squares 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)))))
;;; Ex 1.4
;;;
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
; b is added to a when b is positive
; otherwise it is subtracted which is equivalent to adding the absolute value of b
;;; Ex 1.5
;;
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
; Applicative order: (test 0 (p)) => 0
; Normal order: (test 0 (p)) => infinite loop
(define (sqrt x)
(sqrt-iter 1.0 x))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (square x) (* x x))
;;; Ex 1.6
;;
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
;(define (sqrt-iter guess x)
; (new-if (good-enough? guess x)
; guess
; (sqrt-iter (improve guess x)
; x)))
;
; sqrt-iter will never terminate : the first call to new-if will evaluate the else clause which is a call to sqrt-iter
; sqrt-iter
; new-if
; sqrt-iter
; ...
;;; Ex 1.7
;;
; good-enough? isn't accurate for values much smaller than the tolerance level.
(define (sqrt-gap x)
(sqrt-iter-gap 1.0 0 x))
(define (sqrt-iter-gap guess last-guess x)
(if (good-enough-gap? guess last-guess x)
guess
(sqrt-iter-gap (improve guess x)
guess
x)))
(define (good-enough-gap? guess last-guess x)
(< (abs (- guess last-guess)) (/ guess 100000)))
;;; Ex 1.8
;;
(define (cube-root x)
(cube-root-iter 1.0 0 x))
(define (cube-root-iter guess last-guess x)
(if (good-enough-gap? guess last-guess x)
guess
(cube-root-iter (improve-cube guess x)
guess
x)))
(define (improve-cube guess x)
(/ (+ (/ x (square guess))
(* 2 guess))
3))
No comments. Sign up or log in to comment 
1.1: 10 12 8 8 6 a b 24 4 16 6 16 1.4: Use the sign of b to determine whether to add or subtract it, hence the effect of adding b's absolute value. 1.5: In an applicative order interpreter, the y in the second half of the if condition won't be expanded, so the result will be 0. In a normal order interpreter, attempting to expand the function test will result in an error. 1.6: Without a special instruction to short-circuit the 'else', the new-if expands an endless loop of good-enough? tests. (/ (+ 5 (/ 1 2) (- 2 (- 3 (+ 6 (/ 1 3)))))
(* 3 (- 6 2) (- 2 7)))
(define (sum-of-squares x y)
(+ (* x x)
(* y y)))
(define (sum-of-largest-squares x y z)
(cond ((and (< x y) (< x z)) (sum-of-squares y z))
((and (< y x) (< y z)) (sum-of-squares x z))
((else (sum-of-squares x y))))
)
(define (cube x) (* x x x))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess))
3))
(define (cube-iter guess x)
(if (good-enough? guess x)
guess
(cube-iter (improve guess x) x)))
(define (cubert x) (cube-iter 1.0 x))
No comments. Sign up or log in to comment 
;; Exercise 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) (( b 0) + -) a b) The problem reduces to the evaluation of a combination of two operands and an operator: (if (> b 0) + -). The operator is a compound expression which adds a and b, for b positive, otherwise the operator subtracts b from a. ;; Exercise 1-5 (test 0 (p)) normal-order results in expansion (if (= 0 0) 0 (p)) followed by the evaluation of the if expression, and finally the interpreter prints the value 0. applicative-order the intepreter will first try and evaluate the subexpression (p). Which is a procedure defined as: (define (p) (p)) The definition defines the procedure (p) as (p), which cannot be further expanded. The interpreter will loop indefinitely. ;; Exercise 1-6 The interpreter bombs out with the message: ;Aborting!: maximum recursion depth exceeded The new definition, new-if, only works if the operands are values. This means (new-if...) keeps on calling (sqrt-iter ...), improving the guess, but never tests that guess in the cond form because the procedure (sqrt-iter.. ) it never becomes a value. ;; Exercise 1-7 For small numbers, a precision of one thousandth may not be good enough. For example if we try and find the root of a millionth: (- 0.000001 (square (sqrt 0.000001))) ;Value: -9.762285838805523e-4 we get an unacceptable error, hundreds of times larger than the orginal x of a millionth. (define (square x) (* x x)) (define (sqrt-iter guess x) (if (good-enuf? guess x) guess (sqrt-iter (improve guess x) x))) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enuf? guess x) (< (/ (abs (- guess (improve guess x))) guess) 0.001)) Using our new procedure definition of (good-enuf? ..) (- 0.000001 (square (sqrt 0.000001))) ;Value: -1.1080488810337509e-9 has an error 1000s of times smaller than the original x of a millionth. For large numbers and limited precision, we could have a situation where there is a gap between interpreter's number and our real number. For example the interpreter here, when looking at the number, one-hundred thousand trillion: (- 100000000000000.0099 100000000000000) ;Value: .015625 gives an error greater than the real error. (Equally the error could have been smaller than the real error.) This means for large numbers we don't know the "goodness" of the calculated root. ;; Exercise 1-8 (define (square x) ( x x)) (define (cube x) ( x x x)) (define (cuberoot-iter guess x) (if (cuberoot-good-enough? guess x) guess (cuberoot-iter (cuberoot-improve guess x) x))) (define (cuberoot-improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (cuberoot-good-enough? guess x) (< (abs (- (cube guess) x)) 0.001)) (define (cuberoot x) (cuberoot-iter 1.0 x)) (cuberoot 27) ;Value: 3.0000005410641766 (cuberoot (cube 1000)) ;Value: 1000. No comments. Sign up or log in to comment 
Slow enough for ya? Hopefully I'll be able to make some time for the next one. ;;Ex. 1.1
;;* 10
;;* 12
;;* 8
;;* 3
;;* 6
;;*
;;*
;;*19
;;* #f
;;* 4
;;* 16
;;* 6
;;* 16
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.3
(define (SOS-2OF3 a b c)
(- (+ (square a) (square b) (square c))
(square (cond ((and (<= a b) (<= a c)) a)
((<= b c) b)
(else c)))))
;Don't forget about cases of equivalence!
;;or even simpler
(define (SOS-2LARGEST a b c)
(- (+ (square a) (square b) (square c)) (square (min a b c))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.4
;;Given two numbers a and b, if b is greater than 0 it will return a+b and
;;if b is less than or equal to zero it will return a-b.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.5
;;An applicative-order interpreter will first evaluate 0 and (p), sending
;;it into an infinite loop. A normal-order interpreter will expand the
;;body of test before evaluating. As the <alternative> of an if statement
;;does not evaluate if the <predicate> is true, (p) is never evaluated and
;;the program returns 0.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.6
;;If and cond are special forms such that all operands are not necessarily ;;evaluated.
;;As new-if is evaluated as a regular combination, square-iter is
;;evaluated before it is expanded into a cond and the program enters an
;;infinite loop.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.7
;;Good enough clearly fails for numbers near .001. For an example of a
;;square root we can easily do in our head:
(good-enough? .0001 .0001)
>#t
;;;;;;;;;;;;;;;;;
;;A different but related problem occurs with large numbers. If the
;;square root of a number contains too many digits for scheme to store its
;;thousands place, good-enough? will not be able to reach the answer to
;;within .001 and our program will iterate forever.
;;
;;A better test might be:
;;;;;;;;;;;;;;;;;
(define (good_enough_imprv? old_guess new_guess)
(< (abs (/ (- new_guess old_guess) old_guess)) .00001))
;; I gave it some extra precision as we are now talking relative
;;precision vs. absolute precision. Generally, when talking about square
;;roots of order 10^3, I would like to be correct to .01, giving 10^-5 for
;;my desired precision
(define (average x y) (/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter new_guess old_guess x)
(if (good_enough_imprv? old_guess new_guess)
new_guess
(sqrt-iter (improve new_guess x) new_guess x)))
(define (my_sqrt x)
(sqrt-iter 1.0 2.0 x))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.8
(define (improve-cbrt guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (cbrt-iter new_guess old_guess x)
(if (good_enough_imprv? old_guess new_guess)
new_guess
(cbrt-iter (improve-cbrt new_guess x) new_guess x)))
(define (my_cbrt x)
(cbrt-iter 1.0 2.0 x))
No comments. Sign up or log in to comment 
A little late, but had no time :/
* Exercise 1.2
;; 5+4+(2-(3-(6+4/5)))
;; -------------------
;; 3*(6-2)*(2-7)
(/
(+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7))
)
* Exercise 1.3
(define (max x y z)
(cond
((and (> x y) (> y z))
(+ (* x x) (* y y)))
((and (> x y) (> z y))
(+ (* x x) (* z z)))
((and (> y x) (> z x))
(+ (* y y) (* z z)))
)
)
* Exercise 1.7
(define (sqrt-iter2 old guess x)
(if (good-enough2? old guess x)
guess
(sqrt-iter2 guess (improve guess x) x)))
(define (good-enough2? old guess x)
(< (abs (- 1 (/ guess old) ))
0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (average guess x)
(/ (+ guess x) 2))
(define (raiz2 x)
(sqrt-iter2 100 1.0 x))
* Exercise 1.8
(define (cuberoot x)
(cuberoot-iter 100.0 1.0 x))
(define (cuberoot-iter old guess x)
(if (good-enough old guess x)
guess
(cuberoot-iter guess (improve guess x) x)))
(define (good-enough old guess x)
(< (abs (- old guess)) 0.001))
(define (improve guess x)
; ((x/y^2) + 2y) / 3
(/
(+
(* 2 guess)
(/
x
(square guess)))
3))
No comments. Sign up or log in to comment 
Exercise 1.1, in order:10 12 8 3 6 (Nothing) (Nothing) 19 f4 16 6 16 Exercise 1.2:(/ (+ 5 4 (- 2 (- 3 (+ 6 4/5)))) (* 3 (- 6 2) (- 2 7))) Exercise 1.3:; subtracts the square of the minimum from the sum of all squares (define (ex13 a b c) (let ((min (min a b c)) (sq (lambda (x) (* x x)))) (- (+ (sq a) (sq b) (sq c)) (sq min)))) Exercise 1.4:The if function returns a procedure in either case, but causes the ultimate expression to be (+ a b) in the case of b > 0, and (- a b) in the case of b <= 0. Exercise 1.5:If the interpreter uses applicative-order evaluation, it will never return, stuck in the recursion of p. If it is using the normal-order evaluation (or lazy?) it will not even evaluate p and just return 0. Exercise 1.6:The new-if produces an infinite recursive loop, because it is evaluating both arguments. Exercise 1.7:Statements: 1) The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. A) The floating point numbers (presumably being used) are not always able to represent the exact decimal representation. 2) Also, in real computers, arithmetic operations are almost always performed with limited precision. A) Same as last answer, for example a 64 bit floating point (IEEE 754 binary64) will support 52+1 digits in base 2, with an exponent from -1022 to +1023. 3) This makes our test inadequate for very large numbers. A) Large numbers will suffer the same problem if it is beyond the precision limit. Some examples of failure: (sqrt-iter 1 0.000000005) 0.03125005328123188 Answer from calculator.app: 0.000070710678119 For (sqrt-iter 1 60000000000) it will not return for a long time, thinking the high number results in too many iterations. Numbers as low as 600000 show the length of time increasing. -- Unable to finish the rest with available time. No comments. Sign up or log in to comment 
Ex. 1.1 10 -> 10 (+ 5 3 4) -> 12 (- 9 1) -> 8 (/ 6 2) -> 3 (+ (* 2 4) (- 4 6)) [ = 8 + -2 = 6 -> 6 (define a 3) -> 3 (define b (+ a 1)) -> 4 (+ a b ( a b)) [ = ( 3 + 4 + (34)) = 7 + 12 = 19] -> 19 (= a b) -> #f (if (and (> b a) ( 4 skipped rest Ex. 1.2. skipped Ex. 1.4. The defined function adds the absolute value of b by testing if b is greater than zero. If true, the function returns a + b. If b is less than zero, the function returns a - b. Ex. 1.5. Don't really get it. Ex. 1.6 I don't get it... I cheated and looked at eplanation in forum. Sort of get it, will look at other people's answers Ex 1.7 I'm too tired to answer this effectively right now, but I understand the idea. I like the alternative good-enough test: It asumes that if the guesses aren't changing much, than you must be close to the number. This seems reasonable. ; Ex. 1.3. (define (exerc3) (lambda (a b c) (define (square z) (z*z)) (cond (and (< c a) (< c b)) (+ (square a) (square b)) (and (< b a) (< b c)) (+ (square a) (square c)) (else (+ (square b) (square c))) ) ) ) ; Ex. 1.8 (define (cbrt-iter guess x) (if (cbrt-good-enough? guess x) guess (cbrt-iter (cbrt-improve guess x) x))) (define (cbrt-improve guess x) (avg guess (/ (+ (* guess 2) (/ x (square guess))) 3))) (define (avg x y) (/ (+ x y) 2)) (define (square x) (* x x)) (define (cube x) (* x x x) (define (cbrt-good-enough? guess x) (< (abs (- (cube guess) x)) 0.001))) (define (cbrt x) (cbrt-iter 1.0 x)) Comments:
Sorry for beign kind of lazy with this assignment. I had family in town this week. I'll try to be good for the rest of the course! 
No problem. I understand how that goes. What you completed looks good. 
This is my first shot at lisp (or a programming course of any kind) but I enjoyed it. Also, sorry if the formatting is crap. Exercise 1.110 12 8 3 6 "a --> 3" "b --> 4" 19 f 4 16 6 16 Exercise 1.2(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 (- 2 7)))) Exercise 1.3(define (sumsq x y z) (if (> x y) (if (> y z) (+ ( x x) ( y y)) (+ ( x x) ( z z))) (if (or (> z y) (> z x)) (+ ( z z) ( y y)) (+ ( x x) ( y y))) ) ) Exercise 1.4The procedure uses a conditional, in this case the if statement, in the place of an operator. This allows the function to evaluate the statement b>0 before determining which operator should be used in combining a and b. Exercise 1.5Applicative order evaluates all operators and operands before applying the resulting procedures. This causes the infinite loop procedure (p) to be evaluated before the if statement. If the interpreter used normal evaluation the if statement would be evaluated before the (p) procedure was called and would cause the program to bypass (p) and return 0. Exercise 1.6Applicative order evaluation will cause both the then-clause and the else-clause to be evaluated which will lead to infinite recursion as the else clause has no exit point. Exercise 1.7For any number smaller than the cut off given in good-enough? the sqrt function will be inaccurate as it will stop once the square of the guess is less than the cut off. For large numbers, the number of iterations necessary to find an acceptable answer will lead to the accumulation of small arithmetic errors that are added in each step. ##Exercise 1.7 - Code
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess guess2)
(< (abs (- guess guess2)) (* 0.00001)))
(define (sqrt-iter guess x guess2)
(if (good-enough? guess guess2)
guess
(sqrt-iter (improve guess x)
x guess)))
(define (sqrt x)
(sqrt-iter 1.0 x 1.0))
##Exercise 1.8
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3)
)
(define (good-enough? guess guess2)
(< (abs (- guess guess2)) (* 0.00001 guess)))
(define (sqrt-iter guess x guess2)
(if (good-enough? guess guess2)
guess
(sqrt-iter (improve guess x)
x guess)))
(define (sqrt x)
(sqrt-iter 1.0 x 3.0))
Comments:
Hey TajMaholla, nice job. I'm glad you decided to give it a shot. Lisp is a fun language to learn. Looks like you've nailed those problems. Good job. 
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))
Comments:
Nice job. Your work looks good. Keep pondering 1.5. I think you're close, just read over the section a little more and you should get it.
Ah, I think I understand 1.5 now. I downloaded DrScheme (much better then the command line thing I was using!) and ran the debugger, it never gets to the if statement because applicative order wants to expand both 0 and (P) before looking substituting them in for x and y in the definition for test. As soon as it tries to evaluate p it gets caught in an infinite recursive loop. The normal-order method will simply pass in 0 and (P) into the definition for test, and because (P) is not used unless the else is needed, it is never evaluated, because if is a treated as a special case, right? 
Ex 1.2(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (6-2) (2-7))) ======== Ex 1.3 ======== (define (square x) (* x x)) (define (sum-of-squares x y) (+ (square x) (square y))) (define (f i j k) (cond (and ( ) ) add a to the absolute value of b if b is greater than 0 the operand is +. Else, the operand is -. if the operand is + a and b are added. if the operand is - a and b are subtracted. b is a negative number so this is the same as adding b's absolute value. ======== Ex 1.5 ======== app order: p keeps on trying to be defined, but isn't normal: 0 p never tries to get defined ;**late ex 1.8**
(define (cube-iter guess x)
(if (good-enough? guess x)
guess
(cube-iter (improve guess x)
x)))
;this should be improved!
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (abs x)
(if (< x 0)
(- x)
x))
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3)
(define (cube x) (* x x x))
(define (cuberoot x)
(cube-iter 1.0 x))
Comments:
Good start redmix. Try also browsing over other people's assignments to get a feel for how the other problems were solved. It will help to understand them for future assignments. 
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)
Comments:
Nice. I like how you did 1.3 and 1.6. That looks like the cleanest way to break up those functions.
Oh, wait I was confused on 1.6. Exercise 1.6 is related to new-if, not sum of squares. You may want to check that one again.
Thanks kday, pasted in the wrong text. 
(define (good-enough? guess x) (< (abs (- (improve guess x) guess)) 0.001)) * 1.3
(define (max2sqr a b c) (cond
((or (and (>= a b) (>= b c)) (and (>= b a) (>= a c))) (+(* a a) (* b b )))
((or (and (>= a c) (>= c b)) (and (>= c a) (>= a b))) (+(* a a) (* c c )))
((or (and (>= b c) (>= c a)) (and (>= c b) (>= b a))) (+(* b b) (* c c )))
))
* 1.8
(define (cube x)
(* x x x))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (sqrt-cube-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-cube-iter (improve-cube guess x)
x)))
(define (improve-cube y x)
(/ (+(/ x (* y y))(* 2 y)) 3))
(define (my-sqrt-cube x)
(sqrt-cube-iter 1.0 x))
ex1.1 10; 12; 8; 3; 6; 19; #f; 4; 16; 6; 16 ex1.2 (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 3))))) (* 3 (- 6 2) (- 2 7))) ex1.4 if b > 0 the procedure simplifies to (+ a b) if b >= 0 it simplifies to (- a b) the end result is the procedure adds the absolute value of b to a ex1.5 Applicative order only evaluates the expression when it is used. Result is 0. Normal order expands all expressions and then colapses them. Result is endless recursion. ex1.6 new-if is not a special form. The arguments to new-if are calculated before new-if is called. One of the arguments is another call to new-if resulting in endless recursion. ;1.3
(define (f a b c)
(cond ((and (>= a c) (>= b c)) (+ (* a a) (* b b)))
((and (>= a b) (>= c b)) (+ (* a a) (* c c)))
((and (>= b a) (>= c a)) (+ (* b b) (* c c)))))
;1.7
(define (sqrt-iter old-guess guess x)
(if (good-enough? old-guess guess)
guess
(sqrt-iter guess
(improve guess x)
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? old-guess guess)
(< (abs (- old-guess guess)) (/ guess 1000)))
(define (sqrt x)
(sqrt-iter 1.0 (improve 1.0 x) x))
;1.8 replace improve in sqrt with
(define (improve guess x)
(/ (+ (/ x (* guess guess))
(* 2 guess))
3))
Exercise 1.1
Exercise 1.4 This procedure adds the absolute value of b to the value of a. If b is positive, it adds a and b. If b is negative it subtracts b from a. Exercise 1.5 Normal order evaluation will cause the program to return 0, because test will be evaluated before p is expanded. Applicative order evaluation will cause the interpreter to attempt to expand all the functions before evaluating them. Since p calls itself in an infinite loop, this program will never halt if evaluated by an applicative order interpreter. Exercise 1.6 If the interpreter is using applicative order evaluation the program will never halt. This is because in the original program, if would have forced the interpreter to evaluate good-enough? which would eventually return true and halt the program, but with new-if, sqrt-iter is endlessly expanded and good-enough? is never evaluated. Exercise 1.7 good-enough? tests the guess to within 0.001 of x, so if x is significantly less than 0.001 good-enough? will return true even if the guess is not close to the true root of x. If the number is large it will be dominated by rounding error, and good-enough? will cause the program to continue to attempt improve guess to within 0.001 of x even if guess is not approaching x because of error. (code) The updated program only returns guess when guess is relatively stable from one iteration of the program to the next, it will therefore be at least as accurate for small and large numbers as it is for medium sized ones. Exercise 1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
Exercise 1.3
(define (a_procedure x y z)
(define (square x)
(* x x))
(cond ((and (>= x z) (>= y z)) (+ (square x) (square y)))
((and (>= x y) (>= z y)) (+ (square x) (square z)))
((and (>= y x) (>= z x)) (+ (square y) (square z)))
))
Exercise 1.7
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (square x)
(* x x))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (good-enough? old-guess new-guess)
(< (abs (- old-guess new-guess)) 0.001))
(define (sqrt-iter old-guess new-guess x)
(new-if (good-enough? old-guess new-guess)
new-guess
(sqrt-iter new-guess (improve new-guess x)
x)))
(define (new-sqrt x)
(sqrt-iter 1.0 2.0 x))
Exercise 1.8
# As above except:
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
Comments:
Homework looks great. For 1.7, it looks like you understand the problem with small and big numbers. However, I'm not sure if your new good-enough fixes the problem. For example, I don't think it will work for (new-sqrt 0.0001). See PNuts's assignment for how I think it's supposed to be done. Somewhere there needs to be a division of the change in the guesses by the new-guess so that there can be a normalized comparison that works for numbers of any magnitude. ;PNuts version of the improved good-enough?: (define (good-enough? guess prev) (< (abs (- 1 (/ guess prev))) 0.001)) ;My version of the improved good-enough?: (define (good-enough? old-guess new-guess) (< (abs (/ (- old-guess new-guess) new-guess)) .001))
1.1 1. 10, 12, 8, 3, 6, "a-->3", "b-->4", 19, #f, 4, 16, 6, 16 1.2. (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))) (* 3 (- 6 2) (- 2 7)) 1.4 The operator can be either + or -, depending on the value of b. If b is greater than zero, it's added to a. If b is less than zero, it's subtracted from a. The result is the same as adding the absolute value of b to a. 1.5 If it's applicative order, it will execute the arguments of test first. That means it will execute (p), which will result in an infinite loop. If it's normal order, the if statement will be executed first, and will return zero immediately. (p) will never be executed. 1.6 'new-if' doesn't get a chance to evaluate because its arguments are executed first and hit the max recursion depth before returning a value. That's why if is provided as a special form. ;;;;;;;;;;;;;;;;;;;;;
;;; 1.3:
;;;;;;;;;;;;;;;;;;;;;
(define (ss 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)))))
(ss 1 2 3)
;;;;;;;;;;;;;;;;;;;;;;;;
;;; 1.7:
;;;;;;;;;;;;;;;;;;;;;;;;
(define (good-enough? old-guess new-guess)
(< (abs (/ (- old-guess new-guess) new-guess)) .001))
(define (abs x)
(if (> x 0)
x
(* x -1)))
(define (sqrt x)
(sqrt-iter 0.1 1.0 x))
;;;;;;;;;;;;;;;;;;;;;
;;; 1.8:
;;;;;;;;;;;;;;;;;;;;
(define (cubert x)
(cubert-iter 0.1 1.0 x))
(define (cubert-iter old-guess new-guess x)
(if (good-enough? old-guess new-guess)
new-guess
(cubert-iter new-guess (improve-cube new-guess x)
x)))
(define (improve-cube guess x)
(/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
(define (good-enough? old-guess new-guess)
(< (abs (/ (- old-guess new-guess) new-guess)) .001))
(define (abs x)
(if (> x 0)
x
(* x -1)))
(define (sqrt-iter old-guess new-guess x)
(if (good-enough? old-guess new-guess)
new-guess
(sqrt-iter new-guess (improve new-guess x)
x)))
Comments:
I think everything in here works, but if someone has feedback I'd be glad to hear it.
Looks great. You might include the new three input sqrt-iter function for 1.7 Can I ask why you used 0.1 for the starting old-guess input? I don't think it is wrong I was just wondering if you had a reason for using it instead of 1.0 like the new-guess input.
Thanks for the comment. I forgot about the new three input sqrt-iter function. I'll try to add that in there for 1.7. Well, for the old-guess input, I had to pick something that was significantly different from 1.0. This good-enough? function that I wrote took two guesses as input, the old one and the new one. When I initialize the sqrt-iter function, I don't have an old guess, so I just picked one that would make good-enough evaluate to false. So I am using 1.0, but I also need to add another one, and I just randomly chose 0.1.
Cool, yeah that makes a lot of sense. 
1.1 10 12 8 3 6 none none 19 false 4 16 6 16 1.2 (Couldn't really read it, but if my numbers are correct): (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7))) 1.4 (define (a-plus-abs-b a b) ((if (> b 0) + -) a b)) The "if" will return the + operator if b is positive, thus the procedure returns a + b if b is positive. The "if" will return the - operator if b is negative (or zero), thus the procedure returns a - b. Subtracting a negative number is the same as adding the absolute value of that number, so this procedure will return the same value for a given and and either +/-b. Just like the name says. 1.5 In applicative order, the p is evaluated, but the definition is recursive, so it will continually be called, resulting in an infinite loop. In normal order, the p never gets evaluated because the first condition of the test is true, and thus returns 0. 1.6 Similar to the answer to 1.5, the recursive function is continuously evaluated before the test conditions are checked and an infinite loop condition is reached. 1.7 For small values, the result is off by a lot (ie, sqrt .00001 => .031356) and large values never finish. Changing to the new version gives a better value, for small numbers (ie sqrt .0001 => .00316) and large values actually finish. 1.8 procedure good-enough? doesn't change *1.3*
(define (max-sum-of-squares a b c)
(cond ((and (>= a c) (>= b c)) (+ (square a) (square b)))
((and (>= a b) (>= c b)) (+ (square a) (square c)))
(else (+ (square b) (square c)))))
*1.7*
(define (sqrt x)
(sqrt-iter 1.0 0 x))
(define (sqrt-iter guess old-guess x)
(if (good-enough? guess old-guess)
guess
(sqrt-iter (improve guess x) guess x)))
(define (good-enough? guess old-guess)
(< (abs (- (/ (- old-guess guess) guess))) .0001))
*1.8*
(define (cube-rt-iter guess old-guess x)
(if (good-enough? guess old-guess)
guess
(cube-rt-iter (improve-cube guess x) guess x)))
(define (improve-cube guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (cube-rt x)
(cube-rt-iter 1.0 0.0 x))
Comments:
Wow. Formatting malfunction :)
Just saw the edit button and fixed my formatting. Was that always there? Well, looks good now! Also, realized my good-enough? function in 1.7 has an extraneous subtraction in it. Doesn't affect the result, but it's useless so I fixed it in the code section below (define (good-enough? guess old-guess)
(< (abs (/ (- old-guess guess) guess)) .0001))
No that edit button wasn't always there. Just added last night. Glad you found it.
Nice job. Homework looks great. 
Solutions provided as code with written answers as comments. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.1.scm
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)))
b
a)
;Value: 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
;Value: 16
(+ 2 (if (> b a) b a))
;Value: 6
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
;Value: 16
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.2.scm
(/ (+ 5 4 (- 2 (- 3 (+ 6 4/5))))
(* 3 (- 6 2) (- 2 7)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.3.scm
(define (sum-of-squares x y)
(+ (square x) (square y)))
(define (two-largest f a b c)
(if (and (< a b) (< a c))
(f b c)
(if (< b c) (f a c) (f a b))))
(define (two-largest-sum-of-squares a b c)
(two-largest sum-of-squares a b c))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.4.scm
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
; returns a + |b| by using addition when b is positive and subtraction
; when it is negative
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.5.scm
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))
; applicative-order evaluation: (p) is evaluated before being
; substituted as a parameter for test, causing infinite recursion
; normal-order evaluation: (p) is only substituted for y in test, but
; is never evaluated as the alternative for the if expression is never
; reached
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.6.scm
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
; use of new-if results in error message: Aborting!: maximum recursion
; depth exceeded
; the built-in if is a special form, which only evaluates one of the
; consequent and alternative, but calling new-if evaluates both of its
; parameters
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 x))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.7.scm
(define (sqrt-iter guess prev x)
(if (good-enough? guess prev)
guess
(sqrt-iter (improve guess x)
guess
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess prev)
(<
(abs (- 1 (/ guess prev)))
0.001))
; this form of good-enough? gives more accurate results for small
; numbers, and avoids "Floating-point overflow" for very large numbers
(define (sqrt x)
(sqrt-iter 1.0 -1.0 x))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; ex-1.8.scm
(define (cube-root-iter guess x)
(if (good-enough? guess x)
guess
(cube-root-iter (improve guess x)
x)))
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (cube x)
(* x x x))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (cube-root x)
(cube-root-iter 1.0 x))
Ex 1.4 If Ex 1.5 Applicative-order: infinite loop when evaluating Ex 1.6 In contrast to the special form if, all arguments to ;Ex 1.1
10 12 8 3 6 a b 19 false 4 16 6 16
;Ex 1.2.
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 1 3))))) (* 3 (- 6 2) (- 2 7)))
;Ex 1.3
(define (sqsum-of-two-largest x y z)
(cond ((and (> x z) (> y z)) (* (* x x) (* y y)))
((and (> x y) (> z y)) (* (* x x) (* z z)))
(else (* (* y y) (* z z)))))
;Ex 1.7
(define (sqrt-iter2 new-guess old-guess x)
(if (good-enough2? new-guess old-guess)
new-guess
(sqrt-iter2 (improve new-guess x)
new-guess
x)))
(define (good-enough2? new-guess old-guess)
(< (abs (- new-guess old-guess)) 0.001))
;Ex 1.8
(define (improve-cube guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (cuberoot-iter new-guess old-guess x)
(if (good-enough2? new-guess old-guess)
new-guess
(cuberoot-iter (improve-cube new-guess x)
new-guess
x)))
(define (cuberoot x)
(cuberoot-iter 1.0 2.0 x))
Comments:
your good-enough2? doesn't look for a small fractional change in the guess, but an absolute one - I think my solution below is what was asked for
Ah, thanks for pointing that out :) Note taken.
Yup, other than what PNuts pointed out, it looks like everything works well. Nice job. 
Exercise 1.110 => 10
(+ 5 3 4) => 12
(- 9 1) => 8
(/ 6 2) => 3
(+ ( 2 4) (- 4 6)) => 6
(define a 3) => a
(define b (+ a 1)) => b
(+ a b ( a b)) => 19
(= a b) => false
(if (and (> b a) ( 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a)) => 16(+)
(else 25))
(+ 2 (if (> b a) b a)) => 6
(* (cond ((> a b) a) Exercise 1.2:(/ (+ 5 t (- 2 (- 3 (+ 6 (/ 1 5))))) 3 (- 6 2) (- 2 7)) Exercise 1.3:efine (sum-of-squares a b) (+ (square a) (square b))) (define (sum-of-squares-of-larger-two a b c) (cond ((and ( a c)) (sum-of-squares a b)) ((and (= b c) (> b a)) (sum-of-squares b c)) ((and (= c a) (> c b)) (sum-of-squares c a)) ((and (= a b) ( b 0) + -) a b)) (a-plus-abs-b a b) expands to ((if (> b 0) + -) a b) for -ve b => (- a b) for +ve b => (+ a b) Exercise 1.5:?? Exercise 1.6Infinite loop due to Applicative-order. Exercise 1.7For large numbers, The first iteration produces a very large number (will be slow?)
For small numbers invariably good-enough? will return a false +ve due to the tolerance variable. Comments:
Pretty good. 1.1 through 1.6 are correct. For 1.7, good-enough? fails on small numbers because the tolerance is bigger than the actual numbers being compared, and it fails on big numbers because the computer has rounding errors that are bigger than the tolerance.
Hey, thanks Kday! I wasn't sure about my answer for 1.7. 
1.1 10 12 8 3 6 a b 19 #f 4 16 6 16 1.4 The operator of the procedure a-plus-abs-b is either addition or subtraction depending on an if statement which tests the sign of b. If b is negative, then to add its absolute value to a, the procedure must subtract the negative value. 1.5 An normal-order interpreter would return 0, while an applicative-order interpreter would not return anything. The applicative-order interpreter would substitute and evaluate (p) immediately, which would case an infinite loop at the first step of interpretation. The normal-order interpreter would never reach the alternative of the if conditional and would therefore never evaluate the problematic (p). 1.6 Because new-if is a standard procedure, each operand must be evaluated before the next step of the program. 1.7 For very small numbers, the tolerance of .001 is too large compared to the size of the numbers being tested, stopping the procedure before an adequate guess has been checked. For example, taking the square root of .0001 by this method stops at .0323. For large numbers, the program enters an infinite loop. Eventually a value will be rounded to fit into memory, halting the progress of refining the guess. The improved (good-enough?): (define (good-enough? guess x) (< (abs (- (improve guess x) guess)) (* 0.001 guess))) 1.2 (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7))) 1.3 (define (f a b c) (cond (and (> a c) (> b c)) (+ (* a a) (* b b)) (and (> b a) (> c a)) (+ (* b b) (* c c)) (else (+ (* a a) (* c c))) ) ) 1.8 (define (cuberoot x) (define (improve guess x) (/ (+ (/ x (* guess guess)) (* 2 guess)) 3)) (define (good-enough? guess x) (< (abs (- (improve guess x) guess)) (* 0.001 guess))) (define (cube-iter guess x) (if (good-enough? guess x) guess (cube-iter (improve guess x) x))) (cube-iter 1.0 x) ) 
exercise 1.1 10 ;10 (+ 5 3 4) ;12 (- 9 1) ;8 (/ 6 2) ;3 (+ ( 2 4) (- 4 6)) ;6 (define a 3) (define b (+ a 1)) (+ a b ( a b)) ;7+12=19 (= a b) ;#f (if (and (> b a) ( b a) b a)) ;6 ( (cond ((> a b) a) ;44=16 (( x y) (if (> x z) x (if (> y z) y z)) (if (> y z) y z))) (define (middle x y z) (- (+ x y z) (+ (largest x y z) (- 0 (largest (- 0 x) (- 0 y) (- 0 z)))))) (define (ex1p3 x y z) (+ (square (largest x y z)) (square (middle x y z)))) exercise 1.4 (define (a-plus-abs-b a b) ((if (> b 0) + -) a b)) ;the (if (> b 0) + -) produces a function either + or - so that the correct operation will be done to combine a and b. If b is greater than 0, then a and b are added, otherwise b is subtracted from a which is equivalent to adding the abs of b. Exercise 1.5. What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.) Because evaluation of p is an infinite loop, under applicative order evaluation, this will not terminate, because evaluation of test implies evaluating each argument. Under normal order evaluation p will never be evaluated on (test 0 (p)). Under normal order evaluation, evaluation occurs inside the function definition on each occurrence of the argument. Because of the assumption about if, the else clause is not reached. Exercise 1.6. What happens when Alyssa attempts to use this to compute square roots? Explain. Both the then clause and if clause get evaluated, so the iteration will actually recurse indefinitely. (infinite loop) Exercise 1.7. The problem with good-enough is that the tolerance is fixed at 0.001. So we can't get an answer to accuracy greater than 0.001 so if x is small, then there is a large relative tolerance for error on the answer. At very large numbers there will be rounding. so (nsqrt 0.0000001) is 0.03125 and (nsqrt 0.0001) is 0.03231 (I said nsqrt because scheme didn't seem to let me redefine sqrt.) (nsqrt (expt 10.0 50)) gets into an infinite loop because when you get to a guess of 10^25 and the numerical squaring doesn't give you exactly 10^50, you don't have more significant figures to add, and there isn't enough precision to meet the stopping tolerance. Following the directions to track the changes in the guess, here is an improved version of sqrt-iter that does solve both problems, (at least the examples I mentioned earlier): (This implementation does have a small performance penalty, in that the guess is computed twice. My excuse is that we haven't covered let yet, and the corresponding lambda implementation of let would make this pretty difficult to read at this point.) (define (sqrt-iter guess x) (if (<= (abs (- guess (improve guess x))) (* 0.0001 guess)) guess (sqrt-iter (improve guess x) x))) Exercise 1.8. since square root used: (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (define (square x) (* x x)) (define (nsqrt x) (sqrt-iter 1.0 x)) I now define for cube root: (define (cube-good-enough? guess x) (< (abs (- (* guess (square guess)) x)) 0.001)) (define (cube-improve guess x) (/ (+ (* 2 guess) (/ x (square guess))) 3)) (define (cube-iter guess x) (if (cube-good-enough? guess x) guess (cube-iter (cube-improve guess x) x))) (define (ncubert x) (cube-iter 1.0 x)) Comments:
Nice job! I pointed this out in another homework that it would be nice to see the fixed good-enough? function that you did for 1.7 used in 1.8 so that it also works for small and big numbers. Just a minor thing. 
1.1 10 12 8 3 6 a b 19 f4 16 6 16 ; 1.3
(define (square a)
(* a a))
(define (max-squares a b c)
(- (+ (square a) (square b) (square c))
(square (min a b c))))
; 1.7
(define (good-enough? guess x)
(< (abs (- (square guess) x))
(* 0.001 x)))
; 1.8
(define (cube x)
(* x x x))
(define (cube-approx y x)
(/ (+ (/ x (square y))
(* 2 y))
3))
(define (good-enough? guess x)
(< (abs (- (cube guess) x))
(* 0.001 x)))
(define (cbrt-iter guess x)
(if (good-enough? guess x)
guess
(cbrt-iter (cube-approx guess x)
x)))
(define (cbrt x)
(cbrt-iter 1.0 x))
Comments:
Nice job. I like your solution to 1.7. It's cleaner than what I ended up doing, which required passing the old value into it. This keeps the same interface while fixing the small number and big number problem.
I don't know that the solution to 1.7 fixes all the problems. It seems like it causes the allowable error to increase with the input size. For an input of 100 the error will be around the square root of .1, for 10,000 it will be around the square root of 10, etc. 
1.1
1.2(/ (+ 5 4 (- 2 (- 3 (+ 6 4/5)))) (* 3 (- 6 2) (- 7 2))) 1.4Adds absolute value of b by subtracting b from a if it is negative otherwise adding the a and b 1.5The expression will not evaluate in an interpreter that uses applicative order. In normal order the expression will evaluate to 0. In an applicative order interpreter 0 and (p) are evaluated prior to their binding in test; in a normal order interpreter the arguments are not evaluated until they are used inside the function test. In essence in normal order all forms are special forms. 1.6The function will never return since it evaluates both the then-clause and else-clause prior to the call the function new-if. ; 1.3
(define (Exercise-1.3 x y z)
(cond ((and (< z y) (< z x))
(+ (* x x) (* y y)))
((and (< y z) (< y x))
(+ (* x x) (* z z)))
(else
(+ (* y y) (* z z)))))
(define (sqrt-iter-2 guess x prev)
(if (good-enough-2? guess prev)
guess
(sqrt-iter-2 (improve guess x) x guess)))
(define (good-enough-2? guess prev)
(< (abs (/ (- guess prev) guess)) 1/100))
; 1.8
(define (improve-cubed-root guess x)
(average guess (/ (+ (/ x (* guess guess)) (* 2 guess)) 3)))
(define (good-enough-cubed? guess x)
(< (abs (- x (* guess guess guess))) .001))
(define (cubed-root guess x)
(if (good-enough-cubed? guess x)
guess
(cubed-root (improve-cubed-root guess x) x)))
Comments:
Nice job. It all looks good. For 1.8, I see your good-enough-cubed? uses the same subtraction method as the initial one for the good-enough? function that has problems for large and small numbers. A small improvement would have been to use the good-enough-2? algorithm in the cubed function also. 
Exercise 1.1 10 12 8 3 6 19 4 16 6 16 Exercise 1.2 (/ (+ 5 4 (- 2 (- 3 (+ 6 ( / 4 3))))) (* 3 (- 6 2) (- 2 7))) Exercise 1.3 (define (f x y z) (cond ((and (> x y) (> y z)) (+ ( x x) ( y y))) ((and (> x z) (> y x)) (+ ( x x) ( y y))) ((and (> y x) (> z x)) (+ ( y y) ( z z))) ((and (> z y) (> y x)) (+ ( y y) ( z z))) (else (+ ( x x ) ( z z))))) Exercise 1.4 If b is negative we subtract a and b. Else, we add a and b. Exercise 1.5 Exercise 1.6 (define (f x y z)
(cond ((and (> x y) (> y z)) (+ (* x x) (* y y)))
((and (> x z) (> y x)) (+ (* x x) (* y y)))
((and (> y x) (> z x)) (+ (* y y) (* z z)))
((and (> z y) (> y x)) (+ (* y y) (* z z)))
(else (+ (* x x ) (* z z)))))
Comments:
Oops, I guess I have to finish the HW in one go.
Yeah, sorry the homework doesn't have an edit feature yet. That'll come soon.
I'm going to re-submit my HW. Exercise 1.1: 10, 12, 8, 3, 6, , ,19, #f, 4, 16, 6, 16 Exercise 1.4: If b is negative we subtract a and b. Else, we add a and b. Exercise 1.5: Applicative-order: never stops. The arguments would be evaluated first. So both x and y would be evaluated. y would cause it to be in sort of an infinite loop. Normal-order: 0. Everything is fully expanded and reduced. Since x would get expanded into 0, it would return 0 and stop. Exercise 1.6: Since scheme is using applicative-order evaluation, both the guess and the squrt-iter would get evaluated first. And that would result in the interpreter evaluating it forever. Exercise 1.7: It's not good for small numbers because the tolerance is too big. It's not good for big numbers because the tolerance is too small. So the calculation will run forever. Exercise 1.2:
(/ (+ 5 4 (- 2 (- 3 (+ 6 ( / 4 3))))) (* 3 (- 6 2) (- 2 7)))
Exercise 1.3:
(define (f x y z)
(cond ((and (> x y) (> y z)) (+ (* x x) (* y y)))
((and (> x z) (> y x)) (+ (* x x) (* y y)))
((and (> y x) (> z x)) (+ (* y y) (* z z)))
((and (> z y) (> y x)) (+ (* y y) (* z z)))
(else (+ (* x x ) (* z z)))))
Exercise 1.8:
(define (cube-iter guess x)
(if (good-enough? guess x)
guess
(cube-iter (improve guess x)
x)))
(define (square x) (* x x))
(define (newton-method x y)
(/ (+ (/ x (square y)) (* 2 y)) 3))
(define (improve guess x)
(newton-method x guess))
(define (cube x) (* x x x))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.0001))
(define (cube-root x)
(cube-iter 1.0 x))
Looks good. Your comments on 1.7 were right on, however the problem also asked to implement your own "good-enough?" function to fix those problems. I'm not saying you need to do that because it looks like you've got the hang of this. Just wanted to let you know. Maybe check a few people's assignments to see how they did it. 
Ex 1.1 10 12 8 3 6 no output no output 19 #f 4 16 6 16 Ex 1.4 If b is positive, it adds a and b. If b is negative, it subtracts b from a. This is equivalent to a+|b| Ex 1.5 Applicative order: Infinite loop (p calls p repeatedly) Normal order: 0 (p never actually evaluated) Ex 1.6 Because of applicative order, all arguments are evaluated. Thus, (sqrt-iter (improve guess x) x) will be evaluated no matter what. Therefore, the program enters an infinite loop, as the new call to sqrt-iter will do the same. Ex 1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 8))))) (* 3 (- 6 2) (- 2 7)))
Ex 1.3
(define (f a b c) (if (and (< a b) (< a c)) (+ (* b b) (* c c)) (+ (* a a) (if (< b c) (* c c) (* b b)))))
Ex 1.7
(define (good-enough? guess last) (and (> 1.001 (/ guess last)) (> 1.001 (/ last guess))))
(define (sqrt-iter guess last x)
(if (good-enough? guess last)
guess
(sqrt-iter (improve guess x) guess
x)))
(define (sqt x)
(sqrt-iter 1.0 2.0 x))
Ex 1.8
(define (improve-curt guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (curt x)
(curt-iter 1.0 2.0 x))
(define (curt-iter guess last x)
(if (good-enough? guess last x)
guess
(curt-iter (improve-curt guess x) guess x)))
Comments:
I have a question about your Ex 1.6 answer. I get that applicative order does evaluate all the arguments. But the textbook does state that 'cond' expression terminates after the first predicate is found to be true. I suppose that we're actually talking about what the interpreter is doing, as opposed to what is logically occurring in the new-if procedure (and the cond statement)
My understanding is 'if' and 'cond' are special cases that don't evaluate all the arguments ahead of time. If they didn't then I'm not sure it would be possible to use them in all cases, like 1.6 shows.
Yon, nice homework. And way to go with submitting it extra fast. |
No comments. Sign up or log in to comment