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