FANDOM


Section 1.1: The Elements of Programming Edit

Exercise 1.1 Edit

10
10

(+ 5 3 4)
12

(- 9 1)
8

(+ (* 2 4) (- 4 6))
6

(define a 3)
a

(define b (+ a 1))
b

(+ 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

Exercise 1.2 Edit

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

Exercise 1.3 Edit

This procedure uses a helper procedure, sum-squares:

(define (sum-squares a b) (+ (* a a) (* b b)))

We can now use this in the main procedure:

(define (sum-larger-squares a b c)
  (cond ((= (min a b c) a) (sum-squares b c))
    ((= (min a b c) b) (sum-squares a c))
    ((= (min a b c) c) (sum-squares a c))))

Exercise 1.4 Edit

The if clause applies either + or -, depending on the value of b. If b is positive, (+ a b) is executed; otherwise, (- a b) is executed. This procedure essentially returns the sum of a and the absolute value of b.

Exercise 1.5 Edit

Using applicative-order evaluation, p would keep calling itself forever, resulting in an infinite loop. This will most likely cause the Scheme interpreter to freeze.

Using normal-order evaluation, x gets substituted with 0, so the (= x 0) clause becomes (= 0 0) and returns #t. The expanded expression then becomes (if #t 0 (p)) and returns 0.

Exercise 1.6 Edit

Alyssa's new-if uses applicative-order instead of normal-order evaluation, so sqrt-iter will keep calling itself forever.

Exercise 1.7 Edit

Assuming the appropriate helper procedures have been written, we can define our square root procedure. In our example, we name our procedure my-sqrt to prevent the built-in sqrt from being overwritten. Here, we use a starting guess of one.

(define (my-sqrt x) (sqrt-iter 1 x))

(my-sqrt 25)
5.00002317825395

(my-sqrt 100)
10.0000000001399

(my-sqrt 10000)
100.000000254907

(my-sqrt 0.0000000001)
0.031250001065625

Very small numbers return incorrect results when they are less than the tolerance. Entering (my-sqrt 1e50) causes UCB Scheme to crash.

For the second part of the problem, one simple solution is to check whether the approximation is close enough to the guess. This can be done by modifying the good-enough? procedure:

(define (good-enough? guess x)
  (< (abs (- (improve guess x) guess))
    (abs (* guess 0.001))))

This new version seems to produce more accurate results for small and large numbers:

(my-sqrt 400)
20.0001092577804

(my-sqrt 0.000000000001)
1.00045499080413e-006

(my-sqrt 1e50)
1.00087302912068e+025

Exercise 1.8 Edit

(define (cube-improve guess x)
  (/ (+ (/ x (expt guess 2)) (* 2 guess)) 3))

(define (cube-good-enough? guess x)
  (< (abs (- (cube-improve guess x) guess)) (abs (* guess 0.001))))

(define (cbrt-iter guess x)
  (if (cube-good-enough? guess x)
  guess
  (cbrt-iter (cube-improve guess x) x)))

(define (cube-root x) (cbrt-iter 1 x))

(cube-root 1000)
10.0012053593377

(cube-root 0.0000000000001)
4.64201000474927e-005

(cube-root 1e50)
4.64195345097319e+016

Section 1.2: Procedures and the Processes They Generate Edit

Exercise 1.9 Edit

The first version is a recursive process.

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

9

The second version is an iterative process.

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

9

Exercise 1.10 Edit

(A 1 10)
1024

(A 2 4)
65536

(A 3 3)
65536

The Ackermann function grows very fast. (A 2 5) will cause the Scheme interpreter to crash. The googolplex is completely unnoticeable in comparison to (A 2 6).

(f n) produces f(n) = 2n.

(g n) produces g(n) = 2n.

(h n) produces h(n) = 2h(n-1), which is an exponential stack of 2's of height n. Using Knuth's up-arrow notation, this can be written as 2↑↑n.

Section 1.3: Formulating Abstractions with Higher-Order Procedures Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.