CSC152 2005F, Class 36: Algorithm Analysis

Notes:
* Yes, today should be our last day focusing on algorithm analysis.
* There's been a request that we discuss the daily homework.
* Sorry about the disappearing eboard.  I'm not sure what happened.
* Exam 2 distributed Friday.  Topics: OOP and Algorithms.
* Homework: Probably some recurrence relations 
* Reading available tomorrow 

Overview:
* Analyzing searching methods
  * About Computer.java
  * Sequential search
  * Building a sorted vector
  * Binary search
  * Detour: Testing correctness, rather than speed
* Recurrence relations
  * Strategy
  * Example, revisited
  * More examples

* How might we test sequential search
  * Build a random vector (using randomVector())
  * Pick an element of the vector or an element not in the vector
    * Vs. a "random" element
  * Tried three size vectors
    * Vs. a large variety of sizes of vectors (using a for loop)
      (Similar to the expt examples)
* For a vector of length N, how many steps, ON AVERAGE, would we
  spend finding something in the vector.
  * The length of the vector
  * Half the length of the vector
  * 2/3 the length of the vector
* "Sam, that was a stupid question if we're talking about upper bounds."
  * You are correct.  In that case, we should hope the value is not in the vector.
  * However, we are also using experimental analysis to look at average cases.

* How do we create a random sorted vector?
  * Manually (ouch)
  * Use a similar technique to creating a random vector, but
    put stuff in order as you go (insertion sort)
  * For a vector of length N, fill it with 1, 2, 3, ...., N
  * Start with a random number, and add a random number between
    0 and 10

How do we analyze recursive methods?
* Define a function, t(n), that is supposed to give the running time of our method.
* t(n) will be recursively defined, just as our method is
* Figure out the "base case" for t(n)
  t(0) = .... // most expensive of the base cases
* Figure out the "recursive case" for t(n)
  t(n) = ... t(...) // most expensive of the recursive cases
* Goal: Elminate the t from the rhs of the equality
* Strategy:
  * Repeatedly expand the t on the rhs
  * Look for a pattern
  * Express that pattern in terms of k, the number of times we expanded the right hand side
  * Figure out for which value of k we reach the base case (t(0))
  * Plug that in

(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (sum (cdr lst))))))

t(0) = c 
t(n) = d + t(n-1)

Repeatedly expand right-hand-side
t(n) = d + d + t(n-2) = 2*d + t(n-2)
t(n) = 2*d + d + t(n-3) = 3*d + t(n-3)
t(n) = 3*d + d + t(n-4) = 4*d + t(n-4)

t(n) = k*d + t(n-k)
* Proof by induction that this is correct

For what value of k do we get the base case?  
* t(n-k) = t(0)
* n-k = 0
* n = k

t(n) = k*d + t(n-k) ; substitute n for k
t(n) = n*d + t(n-n) ; simplify
t(n) = n*d + t(0) ; simplify
t(n) = n*d + c ; simplify


(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (if (all-real? lst)
            (+ (car lst) (sum (cdr lst))))
            (error "Bleh"))))

t(0) = c
t(n) = d + e*n + t(n-1)

t(n) = d + e*n + t(n-1)
t(n) = d + e*n + d + e*(n-1) + t(n-2)
t(n) = 2*d + e(n + n-1) + t(n-2)
t(n) = 2*d + e(n + n-1) + d + e*(n-2) + t(n-3)
t(n) = 3*d + e(n + n-1 + n-2) + t(n-3)
t(n) = 4*d + e(n + n-1 + n-2 + n-3) + t(n-4)

FOR FRIDAY
* Finish
* Pick one of the others below and do the same thing
* Have a great day

* Here are some other recurrences to study
* t(n) = d + t(n/2)       // Binary search
* t(n) = d + 2*t(n/2)      // Generic divide-and-conquer
* t(n) = 2*t(n/2)
* t(n) = d + n + t(n/2)   // ???
* t(n) = d + 2*t(n-1)     // Upper bound on Fibonacci
* t(n) = d + 2*t(n-2)     // Lower bound on Fibonacci