CSC151 2007S, Class 56: Review for the Final

Admin:
* Food-like substances
* EC for G-tones/Con Brio at the Burling study break on Monday night at 9. 
* Final Wednesday at 2 pm (or Tuesday at 2 pm).
  * Email me which day

Overview:
* Policies for the final.
* Likely kinds of problems.
* Your Questions

What kinds of questions are likely to be on the exam?
* Code reading
* Lots of recursion over different kinds of structures!
  * Lists
  * Vectors
  * Trees
  * Images
  * Files
  * Numbers
* Some stuff related to searching and sorting
  * Know what sorting is supposed to do
  * Know a little bit about divide-and-conquer
  * Know the role of may-precede?
  * Know about keys
* Higher order stuff
  * Primarily in terms of writing procedures that take other procedures
    as parameters
  * Use and implement map
  * Use compose

What won't be on the exam?
* Things we didn't cover
* Stacks, queues, priority queues, etc.
* The Gimp stuff

Common forms of recursion

(define proc
  (lambda (params)
    (cond
      ((SIMPLE? params)
       (BASE-COMPUTATION params))
      (else
       (COMPUTATION (proc (SIMPLIFY params)))))))

Recursion is primarily concrete when you look at concrete problems

Part of design reflects how you should THINK ABOUT solving recursive
problems:
* When are the parameters simple enough that the answer is straightfoward?
  SIMPLE?
* What is the answer in those cases?
  BASE-COMPUTATION
* If the parameters aren't simple enough, how do I make them "simpler"?
  SIMPLIFY
* Suppose I've solved the simpler problem.  How do I use that to make
  the solution to the more complex problem?
  COMPUTATION

Concrete example: Finding product of non-negative numbers by repeated addition

* A few simple-enough cases
  a*0 = 
  0*b = 
  a*1 =
  1*b = 
* Answers for simple-enough cases
  a*0 = 0
  0*b = 0
  a*1 = a
  1*b = b
* To simplify, subtract 1 from something, say b
* Suppose I know
   a*(b-1)
  What does that tell me about a*b?
  Well, a*(b-1) is a*b - a*1, which is a*b - a.
  If we add a, to a*(b-1), we get a*b


(define multiply
  (lambda (a b)
    (cond
      ((= a 0) 
       0)
      ((= b 0) 
       0)
      ((= a 1) 
       b)
      ((= b 1) 
       a)
      (else
       (+ a (multiply a (- b 1)))))))a

If scratching your head for any of these parts doesn't work, try examples.

Supose a is 5 and b is 6.  Practice tells us that 5*6 = 30
But let's think about the computation

  a*(b-1) = 5*(6-1) = 5*5 = 25.  How do I get from 25 to 30?  Add 5

Suppose a is 10 and b is 23 (10*23=230)
  a*(b-1) 10*(23-1) = 10*22 = 220.  How do I get from 220 to 230?  Add 10

         

Lists

SIMPLE? is almost always (null? lst) or (null? (cdr lst))
SIMPLIFY is almost always cdr
(define proc
  (lambda (lst params)
    (cond
      ((null? lst)
       (BASE-COMPUTATION lst params))
      (else
       (COMPUTATION (proc (cdr lst) params))))))

Numbers

SIMPLE? is almost always (zero? num) or (= num 1)
  * Also (< num some-small-value)
SIMPLIFY can be
  * Subtract 1
  * Divide by 2
  * Almost anything that shrinks the number

Vectors

RECURSION OVER VECTORS REQUIRES A HELPER!
* To keep track of the position
  * WE can use the position to count up from 0 to length-1
    SIMPLE-ENOUGH: (>= pos (length vec))
    SIMPLIFY: add 1
  * We can use the position to count down from length-1 to 0.
    SIMPLE-ENOUGH: (< pos 0) or (= pos 0)
    SIMPLIFY: subtract 1

(define proc
  (lambda (vec params)
    (helper vec (- (vector-length vec) 1) params)))

(define helper
  (lambda (vec pos params)
    (cond
      ((< pos 0)
       (BASE-COMPUTATION vec params))
      (else
       (COMPUTATION (helper vec (- pos 1) params))))))

Problem: vector-sum

(define vector-sum
  (lambda (vec)
    (vector-sum-helper vec (- (vector-length vec) 1))))

(define vector-sum-helper
  (lambda (vec pos)
    (cond
      ((< pos 0)
       0)
      (else
       (+ (vector-ref vec pos)
          (vector-sum-helper vec (- pos 1)))))))

Files NOT ON THE EXAM

Similar to vectors in that we need to do preparatory work
* IN this case, open ports

(define proc
  (lambda (params)
    (cond
      ((SIMPLE? params)
       (BASE-COMPUTATION params))
      (else
       (COMPUTATION (proc (SIMPLIFY params)))))))

Trees

(define proc
  (lambda (tree)
    (if (pair? tree)
        (COMBINE (proc (car tree))
                 (proc (cdr tree)))
        (BASE-COMPUTATION tree))))

Images

Look at the "writing images to files" lab or the answer key for 
exam 3.