Due: Friday, Dec. 9. Please either bring your answers to my office or submit by email. If I am not in my office, ask Jennifer Jacobs to put the exam in my mailbox.
Exercise numbers are from the third edition of Cormen et. al., except as noted. Exercises are reworded somewhat from their source, but looking at the source might help you to understand them.
(17.2-2) Suppose we perform a sequence of n operations on a nonpersistent data structure in which the i-th operation takes time i if i is a power of 2 and take time 1 otherwise. Using the banker's approach, show the amortized cost of each operation. Argue that your analysis is tight. That is, you have not overcounted by more than a constant factor.
(17.3-2) This is the same as the preceding question, but instead of using the banker's approach, use the physicist's approach. That is, find a potential function and use that for the analysis.
(Okasaki, Exercise 10.6) We worked out a persistent data structure that supports empty, isEmpty, head, tail, cons, and ++ in O(1) amortized time per operation. Explain how to add another operation, flatten, to that data structure, where flatten takes a list of lists L and yields the concatenation of all of the lists in L, preserving order. For example, flatten([[1,2,3], [ ], [4,5], [6,7], [ ]) yields [1,2,3,4,5,6,7].
Your implementation of flatten(L) must take amortized time O(1 + e), where e is the number of occurrences of [ ] in list L. Show that it does. Also, addition of this new operation must still allow all other operations to be done in O(1) amortized time each.
(23-1) Second-best spanning tree. Let G be a connected weighted undirected graph with n vertices and e edges, and assume that e ≥ n. Assume that each edge has a distinct weight. (So no two edges have the same weight.)
Define a second-best spanning tree of G as a spanning tree of G that is not equal to the minimum spanning tree of G, but that has smallest possible weight among all other spanning trees.
Show that there is a unique minimum spanning tree of G.
Show that there might not be a unique second-best spanning tree of G, even though all of the edge weights are different.
Let T be the minimum spanning tree of G. Prove that G contains edges (u,v) in T and (x,y) not in T such that removing edge (u,v) from T and adding edge (x,y) to T yields a second-best spanning tree of G.
Let T be a spanning tree of G and, for any two vertices u and v, let max[u,v] denote an edge of maximum weight on the unique path between u and v in T. Describe an O(n2) time algorithm that, given T, computes max[u,v] for every pair of vertices u and v. (That is, it fills in a matrix of all of the max[u,v] values, for all vertices u and v of G.)
Give an efficient algorithm to compute a second-best spanning tree of G.