15-451 Algorithms 02/07/07 RECITATION NOTES ======================================================================= The plan for today is to do some amortized analysis plus practice for the quiz by going over an old one. Also, hand back homeworks. ======================================================================= Before going over the old quiz, here is a problem on Amortized Analysis: In lecture we discussed the "implementing a stack as an array" problem, and decided that doubling the array whenever it gets full does well in an amortized sense. Now, what if we don't want to be space hogs. If we do a lot of pops and the stack gets small, then we want to resize the array to make it smaller. Say k = number of elements and L = size of array. Cost for performing a resize operation is equal to the number of elements moved. Strategy #1: when we pop from k = L/2, then cut the array size in half. Is this a good strategy? [no] Why or why not?? How about cutting in half when pop from k=L/4? Claim: amortized cost is at most 3 per operation. Proof: Consider the interval between successive array resizes. The important point is that after each resize operation, the array is exactly half full. If it's a double, then there must have been at least L/2 pushes since the last resize. This can pay for the work. If it's a halving, then there must have been at least L/4 pops, and these can be used to pay for the resize. If you want to use the bank-account method, you can think of each push or pop as paying $1 to perform the operation and putting $2 in the bank to pay for a possible future resizing. ============================================================================== Old Quiz 1. You can go problem-by-problem, giving the question and then giving students time to work it out, and then having students present their solutions. The most interesting of these is problem 3. Make sure you have time to do that one. Problem 1: solve these recurrences in O notation. (the actual quiz was multiple choice just for grading purposes): T(n) = T(n/3) + T(n/4) + T(n/5) + n T(n) = 5 T(n/5) + n T(n) = 5 T(n-2) + 1 T(n) = T(4n/5) + 1 [solutions: see bottom of page] Problem 2: Suppose that f(n) = O(g(n)). Write ``True'' if the statement below is necessarily true. Otherwise, write ``False'' *and* give a counterexample. Assume f(n),g(n) >= 2 for all n > 1. log f(n) = O( log g(n) ) (f(n))^2 = O( (g(n))^2 ) 2^{f(n)} = O( 2^{g(n)} ) g(n) = O(f(n)) [solutions: see bottom of page] Problem 3: Consider a deterministic Quicksort algorithm that chooses the pivot by running the deterministic Theta(n)-time median-finding algorithm discussed in class. (After all, the median element is the best pivot). a. Write a recurrence for the running time of this algorithm on an array of size n. [Note: you should just view the median-finding algorithm as a linear-time black box; your recurrence shouldn't go into the innards of that algorithm] b. Solve the recurrence in Theta() notation. c. Suppose that instead of using the median, we use the *average* of the numbers as the pivot (i.e., we add up all the numbers and divide by n). Assume that it takes O(n) time to compute the average. What is the worst-case running time of this version of Quicksort, and why? Be explicit about your reasoning. E.g., describe what an array would look like that achieves the worst-case. [solutions: see bottom of page] ======================================================================= ======================================================================= ======================================================================= [problem 1 solutions: O(n), O(n log n), O(5^{n/2}), O(log n).] [problem 2 solutions: T, T, F, F] [problem 3 solutions a: T(n)=2T(n/2)+cn. b: O(n log n). c: Omega(n^2). One array that would cause this is: [n,n^2,n^3,...,n^n]. Another is [1!, 2!, 3!,..., n!]. One that *almost* works but doesn't quite is [1,2,4,8,...,2^n]. ]