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