* 1.9

#+BEGIN_SRC 
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
(+ 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
#+END_SRC
 this impl describes a recursive process.

#+BEGIN_SRC 
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
#+END_SRC
 this impl describes an iterative process

* 1.10
Ackerman's function:
#+BEGIN_SRC scheme
  (define (A x y)
    (cond ((= y 0) 0)
          ((= x 0) (* 2 y))
          ((= y 1) 2)
          (else (A (- x 1)
                   (A x (- y 1))))))
(A 2 4)
#+END_SRC

#+RESULTS:
: 65536

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
(A ... )
65536

(A 0 n): 2n
(A 1 n): 2^n
(A 2 n): 2^2^n

* 1.11
#+BEGIN_SRC scheme
  (define (fn n)
    (if (< n 3)
        n
        (+ (fn (- n 1))
           (* 2 (fn (- n 2)))
           (* 3 (fn (- n 3))))))
  (fn 2)

#+END_SRC

#+RESULTS:

this is the recursive approach. slow with even small numbers
TODO: iterative approach

* 1.12
this is a pascal's triangle

1:        1
2:       1 1
3:      1 2 1
4:     1 3 3 1
5:    1 4 6 4 1
6:  1 5 10 10 5 1

6, 6 = 1
6, 1 = 1
6, 2 = 5
1, 1 = 1

write a procedure that computes the elements recursively

#+BEGIN_SRC scheme
  (define (pascals row num)
    (if (or (= row num) (= num 1) (= row 1))
	1
	(+ (pascals (- row 1) (- num 1))
	   (pascals (- row 1) num))))
  (pascals 6 4)
#+END_SRC

#+RESULTS:
: 10

* 1.17
(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))
#+BEGIN_SRC scheme
  (define (double a)
    (mul a 2))
  (define (halve a)
    (/ a 2))
  (define (fast-mul a b)
  TODO
#+END_SRC

* 1.21
find the lowest common divisor of 199, 1999, 19999
#+BEGIN_SRC scheme
  (define (smallest-divisor n)
    (find-divisor n 2))
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
	  ((divides? test-divisor n) test-divisor)
	  (else (find-divisor n (+ test-divisor 1)))))
  (define (divides? a b)
    (= (remainder b a) 0))

  (smallest-divisor 199)
  (smallest-divisor 1999)
  (smallest-divisor 19999)
#+END_SRC

199:   199
1999:  1999
19999: 7

* linear fibbonacci
alluded to in the lecture, find a fast fibb computation
#+BEGIN_SRC scheme
  (define (fib n)
    (fib-iter n 0 1 0))
  (define (fib-iter n count sum last-sum)
    (if (= count n)
	last-sum
	(fib-iter n (1+ count) (+ sum last-sum) sum)))
  (fib 10)
#+END_SRC

#+RESULTS:
: 55

this is the linear version of the tree reversal from the lecture
for this version,
space = O(1)
time  = O(n)

the version in the lecture has time O(fib(n))
calculating the 10th elem, O(fib(n)): 55 vs O(n): 10