Chapter11:AmortizedAnalysis11.1When the number of trees after the insertions is more than the number before.11.2Although each insertion takes roughly log N?, and each DeleteMin? takes 2log N? actual time, our accounting system is charging these particular operations as 2 for the insertion and 3log N?2 for the DeleteMin.? The total time is still the same; this is an accounting gimmick. If the number of insertions and DeleteMins? are roughly equivalent, then itreally is just a gimmick and not very meaningful; the bound has more significance if, for instance, there are N? insertions and O?(N?/ log N?) DeleteMins? (in which case, the total time is linear).11.3Insert the sequence N?, N? + 1, N? 1, N? + 2, N? 2, N? + 3, ., 1, 2N? into an initially empty skew heap. The right path has N? nodes, so any operation could take (N?) time.11.5We implement DecreaseKey(X, H) as follows: If lowering the value of X? creates a heap order violation, then cut X? from its parent, which creates a new skew heap H?1with the new value of X? as a root, and also makes the old skew heap H? smaller. This operation might also increase the potential of H?, but only by at most log N?. We now merge H? and H?1. The total amortized time of the Merge? is O?(log N?), so the total time of the DecreaseKey? operation is O?(log N?).11.8Forthezig?zig?case,theactualcostis2,andthepotentialchangeis R?f?( X? ) + R?f?( P? ) + R?f?( G? ) Ri?( X? ) Ri?( P? ) Ri?( G? ).This gives an amortized time bound ofATzig?zig? = 2 + R?f?( X? ) + R?f?( P? ) + R?f?( G? ) Ri?( X? ) Ri?( P? ) Ri?( G? )Since R?f?( X? ) = Ri?( G? ), this reduces to= 2 + R?f?( P? ) + R?f?( G? ) Ri?( X? ) Ri?( P? )Also, R?f?( X? ) R?f?( P? ) and Ri?( X? ) Ri?( P? ), soATzig?zig? 2 + R?f?( X? ) + R?f?( G? ) 2Ri?( X? )Since Si?( X? ) + S?f?( G? ) S?f?( X? ), it follows that Ri?( X? ) + R?f?( G? ) 2R?f?( X? ) 2. ThusATzig?zig? 3R?f?( X? ) 3Ri?( X? )11.9(a) Choose W?(i?) = 1/ N? for each item. Then for any access of node X?, R?f?( X? ) = 0, and Ri?( X? ) log N?, so the amortized access for each item is at most 3 log N? + 1, and the net potential drop over the sequence is at most N? log N?, giving a bound of O?(M?log N? + M? + N?log N?), as claimed.(b) Assign a weight of qi?/M? to items i?. Then R?f?( X? ) = 0, Ri?( X? ) log(qi?/M?), so the amortized cost of accessing item i? is at most 3 log(M?/qi?) + 1, and the theorem follows immediately.11.10(a) To merge two splay trees T?1and T?2, we access each node in the smaller tree and insert it into the larger tree. Each time a node is accessed, it joins a tree that is at least-63-twice as large; thus a node can be inserted log N? times. This tells us that in any sequence of N?1 merges, there are at most N?log N? inserts, giving a time bound of O?(N?log2N?). This presumes that we keep track of the tree sizes. Philosophically, this is ugly since it defeats the purpose of self-adjustment.(b) Port and Moffet 6 suggest the following algorithm: If T?2is the smaller tree, insert its root into T?1. Then recursively merge the left subtrees of T?1and T?2, and recursively merge their right subtrees. This algorithm is not analyzed; a variant in which the median of T?2is splayed to the root first is with a claim of O?(N?log N?) for the sequence of merges.11.11The potential function is c? times the number of insertions since the last rehashing step, where c? is a constant. For an insertion that doesnt require rehashing, the actual time is 1, and the potential increases by c?, for a cost of 1 + c?.If an insertion causes a table to be rehashed from size S? to 2S?, then the actual cost is 1 + dS?, where dS? represents the cost of initializing the new table and copying the old table back. A table that is rehashed when it reaches size S? was last rehashed at size S?/ 2, so S?/ 2 insertions had taken place prior to the rehash, and the initial potential was cS?/ 2. The new potential is 0, so the potential change is cS?/ 2, giving an amortized bound of (d? c?/ 2)S? + 1. We choose c? = 2d?, and obtain an O?(1) amortized bound in both cases.11.12We show that the amortized number of node splits is 1 per insertion. The potential func- tion is the number of three-child nodes in T?. If the actual number of nodes splits for an insertion is s?, then the change in the potential function is at most 1 s?, because each split converts a three-child node to two two-child nodes, but the parent of the last node split gains a third child (unless it is the root). Thus an insertion costs 1 node split, amor- tized. An N? node tree has N? units of potential that might be converted to actual time, so the total cost is O?(M? + N?). (If we start from an initially empty tree, then the bound is O?(M?).)11.13(a) This problem is similar to Exercise 3.22. The first four operations are easy to imple- ment by placing two stacks, SL?and SR?, next to each other (with bottoms touching). Wecan implement the fifth operation by usin