1. (a) There are two cases. If an insertion does not require a reallocation, then it takes O(1) actual time, and the potential function changes by +2 = O(1), so the total amortized time is O(1). If it does require a reallocation, it takes O(n) actual time (where n is the number of items prior to the update) and the potential function changes from n to 2, so the total change is 2-n, cancelling the actual time and again giving O(1) amortized time. (b) Again there are two cases. If a deletion does not require a reallocation, it takes O(1) actual time and changes the potential function by +1, so the total is O(1). If it does require a reallocation, then (letting n be the number of items prior to the update) it takes O(n) actual time, and the potential function changes from n to 1, so the total change is 1-n, again cancelling the actual time and giving O(1) amortized time. (c) No. Explanation 1: Because amortized analysis is only valid if you use the same potential function to analyze every operation. Explanation 2: For this problem, it is possible to have a sequence of operations that alternate between insertions and deletions, with the array at the threshold value so that every operation leads to a reallocation. For this sequence of operations, the actual time per operation is Theta(n). It is not possible for the sum of the amortized times, over a sequence of operations, to be less than the sum of the actual times, so it is not possible to come up with an amortized analysis that uses only O(1) time per operation. 2. o /|\ o o o This tree has three children and only four nodes. However in a Fibonacci heap every tree with three children has at least five nodes. 3. (a) Let the two hash functions be h1 and h2. If the three keys x, y, and z have h1(x)=h1(y)=h1(z) and h2(x)=h2(y)=h2(z) then they will cause a failure, and this is the only pattern for three keys that will cause a failure. (b) 1/10000 = 1/10^4. Whatever values are chosen for h1(x) and h2(x), there is a one in ten probability that the same values are chosen for each of h1(y), h2(y), h1(z), and h2(z). Because of 3-independence, it is safe to compute the probability that all of these events happen at once by multiplying together the four 1/10 probabilities. 4. There are four tables of 2^8 entries each, for a total of 1024 random numbers. 5. Use successor(-infinity) to find the highest priority item. 6. The simplest answer is to set w_i = 1/2^i. Then W = sum w_i < 2, so log(W/w_i) < log(2^{i+1}) = i+1. It is also possible to set w_i=1/(i+1)^2; using this choice gives time O(log(i+1)) amortized time per operation, better than the O(i+1) required by the problem. (It is necessary to use 1/(i+1)^2 rather than 1/i^2 to avoid dividing by zero for i=0.) However it doesn't work to use w_i=1/(i+1) because then we would have W=Theta(log n) and log(W/w_i)=O(log i + loglog n), not good enough for small values of i.