15-451 Algorithms 9/22/04 RECITATION NOTES ======================================================================= The plan for today is to do some amortized analysis plus practice for the quiz by going over last year's. Also, hand back homeworks. ======================================================================= Problem 1: 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. Strategy #1: when we pop from k = L/2, then cut the array size in half. Is this a good strategy? 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. ============================================================================== Last Year's 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. Problem 1: solve these recurrences (the actual quiz was multiple choice just for grading purposes): T(n) = 4 T(n/4) + n. T(n) = 16 T(n/4) + n. T(n) = T(n-4) + n^3. T(n) = T(n/4) + T(n/2) + n. Problem 2 (amortized analysis): Suppose we're doing a sequence of operations (numbered 1, 2, 3,...) such that the ith operation: - costs 1 if i is *not* a power of 2, and - costs i if i *is* a power of 2. For example, the following table shows the costs for each of the first few operations: operation number: 1 2 3 4 5 6 7 8 9 ... cost: 1 2 1 4 1 1 1 8 1 ... Give the best upper bound you can on the amortized cost per operation. [quiz was multiple-choice with choices 1,2,3,4,log(n),n] Problem 3: Does there exist an algorithm that makes at most four comparisons to sort any array of size 4? Why or why not? Problem 4: Consider a random permutation of the numbers 1,2,...,n. Let's call a number in this permutation a Biggie if it's greater than all the numbers to its left. Note that the number that ends up in the first position is definitely a Biggie. a) What is the probability that a number in position i is a Biggie? (The positions are numbered from left to right, starting from 1.) b)Building on your answer above, what is the expected number of Biggies in the whole array? ------------------------------- Answers: 1: n*log(n), n^2, n^4, n. 2: Answer is 3. Two natural ways of analyzing are: (a) summing up the totals and dividing by n. In this case, the powers of 2 give at most 1+2+4+8+...+n < 2n, and the non-powers-of-2 give n - log(n) < n, so the total is < 3n, or amortized 3 per operation. (b) the piggy-bank method: if every operation since the last power of 2 pays \$2 extra, that produces enough money to pay for the expensive operation. So, in this accounting, the cheap operations pay \$3, and the expensive operations pay \$2, for an amortized cost < \$3. Also, the answer isn't \$2 since we can see that the first 8 operations cost > 16. 3: No. 4 < lg(4!). [You did this on the mini]. 4a: 1/i. 4b: H_n.