To understand and be able to conduct Amortized Analysis.
Task
- Consider a Binary Representation Heap implementation of Priority Queue. If there are n elements in the heap, then there is a vector X of lg n + 1 arrays.
- X[i] is an array of size 0, or of size 2i
- each X[i] is in sorted order, with X[i][0] being the smallest element in X[i].
- [4 marks] Given any particular n, there is just one "shape" that X can have. What is that shape? I.e., what are the sizes of all the X[i]?
- [4 marks] What is the maximum running time of an insert operation? What is the maximum running time of a findMin operation?
- [8 marks] What is the amortized running time of m operations, where the BinRepHeap starts empty, and the m operations are all insert operations? Use the Accounting Method or the Potential method. You must get a better running time than just the worst case.
- [2 marks] Given that the amortized running time is as you proved above if all operations are inserts, argue that the amortized running time is the same if there are a mix of inserts and find operations.
- [4 marks] The Binary Counter: We used amortized analysis to show that the worst-case amortized running time is Θ(1) per operation, when all the operations are inc operations. Suppose we introduce a Reset operation, which resets all the 1's to 0. Show that the amortized running time is still Θ(1) for a sequence of inc and Reset operations, assuming that the sequence starts with the counter at 0.
- [4 marks] Lemma 22.3 (CLRS) says that any tree in the union-find forest that uses union-by-rank has size(x) ≥ 2rank(x), where x is the root, and size(x) is the number of nodes in the tree rooted at x. Prove this claim.
rank(x) = 0 right after MakeSet(x) is executed, i.e., when x is the root of a tree with just one element.
rank(x) increases by 1 if Link(x,y) is called and both x and y have the same rank, and the Link operation makes x the parent of y. In no other circumstance does the rank of x change.