Topics to know:

• Types of evaluation
• Applicative order evaluation (all arguments must be fully evaluated before being plugged into parameters
• Normal order evaluation (arguments evaluated as needed within body of procedure
• Special Forms: Do not have to adhere to any particular form of evaluation (define, for example)
• Types of processes in recursion
• Recursive processes: eat up memory as deferred operations (such as * in the factorial example) must wait for recursive calls to complete.
• Iterative processes: save on memory by having state variables keep track of what is being computed.
• Orders of growth: How do we characterize the amount of time or space needed to run an algorithm?
• Exponential growth (such as the bad Fibonacci function): O(xn) where x > 1
• Linear growth (such as a generic factorial function): O(n)
• Logarithmic growth (such as searching for a name in a phone book or fast-expt): O(log2n)
• Polynomial growth: O(nk)
• Constant growth (such as with arrays): O(n)
• Procedural abstraction (going from sum to accumulate)
• Procedures that return procedures (such as double, compose, and repeated)

Below is code from review during class

```(require (lib "trace.ss"))  ; for testing only
(define (square x) (* x x))
(define (1+ x) (+ x 1))
(define (2+ x) (+ x 2))
(define (identity x) x)

(define (acc2 combiner id term a next b)
(acc-iter combiner id term a next b))
(define (acc-iter combiner result term a next b)
(cond ((> a b) result)
(else (acc-iter combiner
(combiner (term a) result)
term
(next a)
next
b))))

; (trace acc-iter)
; (trace accumulate)

(define (double f)
(lambda (x) (f (f x))))

;(double 1+) --> (lambda (x) (1+ (1+ x)))
;(double double) --> (lambda (x) (double (double x)))
;(double (double double)) -->
; (lambda (x) ((double double) ((double double) x)))
;(define (f g)
;  (g 2))

; f(g(x))
(define (compose f g)
(lambda (x) (f (g x))))
; repeated (two different ways)
(define (repeated f n)
(lambda (x)
(cond ((= n 0) x)
(else ((compose f (repeated f (- n 1))) x)))))

(define (repeated f n)
(lambda (x)
(cond ((= n 0) x)
(else ((repeated f (- n 1)) (f x))))))

; pi/4: product, pi-term
(define (accumulate combiner id term a next b)
(cond ((> a b) id)
(else (combiner (term a)
(accumulate combiner id term (next a) next b)))))

(define (product term a next b)
(accumulate * 1 term a next b))

(define (pi-term n)
(cond ((odd? n) (/ (+ n 1) (+ n 2)))
(else (/ (+ n 2) (+ n 1)))))

(define (pi/4 terms)
(product pi-term 1 1+ terms))

(define (pi terms)   ; Floating point nice for display purposes
(* 4. (pi/4 terms)))

; An interval abstraction
(define make-interval cons)
(define lower car)
(define upper cdr)

; Another interval abstraction
(define (make-interval lower upper)
(lambda (msg)
(cond ((eq? msg 0) lower)
((eq? msg 1) upper))))
(define (lower interval) (interval 0))
(define (upper interval) (interval 1))

; Bottom line: Use lower and upper.  They work.  No guarantees about
;   how they are written though!
```