## Solution to SICP Exercise 1.12

Solution to Exercise 1.12:

```(define (pascal row col) (cond ((or (= 0 col) (= row col)) 1) (else (+ (pascal (- row 1) (- col 1)) (pascal (- row 1) col)))))```

## Solution to SICP Exercise 1.11

Solution to Exercise 1.11:

A recursive process:

```(define (fr n) (cond ((< n 3) n) (else (+ (fr (- n 1)) (* 2 (fr (- n 2))) (* 3 (fr (- n 3)))))))```

An iterative one:

```(define (fi n) (define (f-iter i f-i-1 f-i-2 f-i-3) (if (> i n) f-i-1 (f-iter (+ i 1) (+ f-i-1 (* 2 f-i-2) (* 3 f-i-3)) f-i-1 f-i-2))) (if (< n 3) n (f-iter 3 2 1 0)))```

## Solution to SICP Exercise 1.10

Solution to Exercise 1.10:
```> (A 1 10) 1024 > (A 2 4) 65536 > (A 3 3) 65536```

`(f n)` computes 2n.

`(g n)` computes 2n for n>0. For n=0, it is 0.

`(h n)` computes h(n) such that if n=0, h(0)=0; otherwise h(n)=2h(n-1).

## Solution to SICP Exercise 1.9

Solution to Exercise 1.9:

The first procedure follows a recursive process:

```(+ 4 5) (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 follows an iterative one:

```(+ 4 5) (+ (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```

## Solution to SICP Exercise 1.8

Solution to Exercise 1.8:

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

``` (define (cube x) (* x x x)) (define (cbrt-iter guess prev-guess x) (if (good-enough? guess prev-guess) guess (cbrt-iter (improve guess x) guess x))) (define (improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (good-enough? guess prev-guess) (< (/ (abs (- guess prev-guess)) guess) 0.001)) ```

```(define (cbrt x) (cbrt-iter 1.0 0.0 x))```

This solution uses the guess evaluation strategy of Exercise 1.7.

It seems to give reasonable results:

```> (cbrt 8) 2.000000000012062 > (cbrt 27) 3.0000005410641766 > (cbrt 64) 4.000000000076121```

## Solution to SICP Exercise 1.7

Solution to Exercise 1.7:

The results for small values become very inaccurate. For example, the root of the square of 0.001, which we might expect to be itself is found to be off by a factor of ~31.3 times.

```> (sqrt (square 0.001)) 0.031260655525445276```

As the values grow larger, the precision of the guess comes into play. Eventually the computer becomes unable to represent the guess to a precision of 0.001. In such cases, the program can endlessly alternate between two guesses that are more than 0.001 away from the true square root. On my x86 machine with DrScheme, this can be seen with the following expression

`> (sqrt 1e13)`

Here is an implementation of `good-enough/` that follows the alternative strategy given in the exercise

```(define (good-enough? guess prev-guess) (< (/ (abs (- guess prev-guess)) guess) 0.001))```

The `x` parameter is replaced by `prev-guess`, which necessitates a change to `sqrt-iter` and `sqrt`, as shown here:

```(define (sqrt-iter guess prev-guess x) (if (good-enough? guess prev-guess) guess (sqrt-iter (improve guess x) guess x)))```

(define (sqrt x)
(sqrt-iter 1.0 0.0 x))

I’ve used an initial `prev-guess` of zero, which ensures that the initial guess of one is never good enough, thus forcing at least one iteration of the algorithm.

This implementation performs much better on the two troublesome examples given above:

```> (sqrt (square 0.001)) 0.0010000001533016628 > (sqrt 1e13) 3162277.6640104805```

## Solution to SICP Exercise 1.6

Solution to Exercise 1.6:

Because `new-if` is a function, both of its parameters are evaluated before the operation is performed. Since one of the parameters is a call to `sqrt-iter`, the first operation of which is a call to `new-if`, an endless loop is formed and the function never completes.

## Solution to SICP Exercise 1.5

Solution to Exercise 1.5:

With applicative-order evaluation, the expression that Ben entered for evaluation will fail to terminate. The reason for this has to do with expression `(p)` evaluating to itself. When evaluating with applicative order, every combination within an expression is evaluated before the expression itself. The `(p)` combination never finishes evaluating because it keeps evaluating to itself.

With normal-order evaluation, the expression will be evaluated to `0`. The reason is that the `(p)` combination is passed to `test` unevaluated. According to normal-order evaluation rules, it isn’t evaluated by the interpreter until its value is needed. The condition of the `if` expression in `test` is satisfied (because the expression `(= 0 0)` evaluates to `#t`, so the `test` procedure evaluates to `0`. There is never any need to evaluate `(p)`.

## Solution to SICP Exercise 1.4

Solution to Exercise 1.4:

If `b` is positive, the `+` operator will be applied to `a` and `b`. Otherwise, the `-` operator will be. This results in the absolute value of `b` always being added to `a`.

## Solution to SICP Exercise 1.3

Solution to Exercise 1.3:

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

``` (define (sum-of-squares x y) (+ (square x) (square y))) ```

```(define (sum-of-squares-of-two-larger 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)))) ```