Final Exam review outline
-------------------------

[~90% of this is recycled from discussion outlines...]



STRUCTURE

do mental type-checking

don't forget about data abstraction!

order-of-growth
    what's n?  how are we measuring the size of the input?

    BASIC tests (these are not complete!) :
        How does doubling the size of the input affect the time/space
         requirements?
            requirements doubled? -------------------------> O(n)
                         quadrupled? ----------------------> O(n^2)
                         increased by a constant amount? --> O(log n)
                         not affected? --------------------> O(1)

        How does increasing the input size by a constant amount affect the
         time/space requirements?
            requirements increased by a constant amount? --> O(n)
                         doubled? -------------------------> O(2^n)
                         tripled? -------------------------> O(3^n)
                         [etc.]

    what's the running time of:
        (define (last-pair lst)
          (if (= (length (cdr lst) 0))
              lst
              (last-pair (cdr lst)) ))

         how would the running time be different if we used
          (null? (cdr lst)) instead of using length?

tree recursion
    common base cases:
        are there more trees in the forest?
        are you at a leaf?
    is it possible to satisfy both base cases simultaneously?
        order your base cases appropriately

    Fall 96 Final Q16. heap?
    Spring 96 Final Q3. path?

DDP
    general idea: data instructs program what to do
        (see Fall 1997 Final, Q4)
    doesn't need to use tables, doesn't need to use put/get

MP
    going from above-the-line OOP to MP and vice-versa
    types that check for operations

conventional/explicit dispatch
    operators that check for types

OOP
    Should you use inheritance?
        Do the involved classes have an isA relationship?
        Do two classes have a hasA relationship?
            Don't use inheritance.  Use local state variables instead.
    shadowing vars
    vars have implicit methods
    class-vars vs. instance-vars

    Spring 95 Final Q6. clubs

environment diagrams
    rules?  what parts of MCE handle each rule?

    exercise: environment diagram for y-combinator

mutation
    if you're using set! on a local var, you're probably doing something
     wrong

streams
    Spring 96 Final Q2. row



INTERPRETATION

evaluators
    ordinary MCE
        representation of frames
        representation of environments
    analyzing evaluator
        separation of analysis from execution
            why did all the drawings of the MCE machine have separate
             inputs for program and data?
        when do we see benefits of analysis?
            when we run analyzed code multiple times
            is there any benefit from:
                A-Eval> ((lambda (x) (* x x)) 5)
                A-Eval> ((lambda (x) (* x x)) 7)
            compare that to:
                A-Eval> (define (square x) (* x x))
                A-Eval> (square 5)
                A-Eval> (square 7)
            could we use memoization?
                yes, but the analyzing evaluator is mysterious enough as it
                 is
    lazy evaluator
        what's delayed?
        when do thunks get forced?
        what's memoized?
        why memoization?
        Explain:
            Lazy> (define count 0)
            Lazy> (define (incr) (set! count (+ count 1)) count)
            Lazy> (incr) ==> 1
            Lazy> (incr) ==> 2
    logo interpreter
        logo-eval vs. eval-prefix vs. eval-line
    amb evaluator
        amb chooses sequentially in left-to-right order
        decision trees
        continuations

logic programming
    query system is a PATTERN MATCHER
    rules
        (rule <conclusion> <premise>)
        recursive rules are like proofs by induction
    variable names
        variables with the same name must match the same item
        variables with different names do NOT have to be different
            use (not (same ?x ?y)) to require difference
    NOT is a FILTER
    rules are not procedures!
    examples
        addition (Fall 97 Final Q11)
        multiplication (Fall 97 Final Q11)
        division (Fall 98 Final Q8)