Practice Problem Set 10
In this week's lectures we saw that it is easy to use path copying to make a fully persistent stack, based on a non-persistent implementation of stacks using singly-linked lists. In problem 1 of Practice Problem Set 1 we saw that the same non-persistent method for stacks can also be easily adapted to implement queues, by maintaining two pointers to the two ends of a singly-linked list, one pointer for enqueue operations and the other for dequeue operations. Explain why combining these ideas does not work: Why does path copying not work well to make that representation for queues into a fully persistent data structure?
Let \(x\) be a node of a binary search tree with parent \(y\), represented using zippers with the finger pointing to \(x\). Suppose we wish to perform a rotation operation (see the lecture notes from week 6), producing a new version of the tree, again with the finger pointing to \(x\). Describe the new nodes that are created by this operation, including the pointers stored at each of these new nodes. (You may need two cases, depending on whether \(x\) is a left or right child of \(y\).)
Suppose that we are using a union-find structure for a family of disjoint sets of elements that have a total ordering (that is, we can compare any two elements and determine which one is smaller, in constant time). We wish to modify the find\((x)\) operation so that, instead of returning an arbitrary member of the set containing \(x\), it always returns the smallest member. Describe a way of performing this modification with the same time per operation (in terms of its \(O\)-notation) as the original union-find data structure.
(Hints: It does not work to change which node gets linked to which in a union in order to make the minimum element be the root of the tree for its set. The reason it doesn't work is that doing this would interfere with the union-by-size property used in the analysis of the data structure. Instead, find a way of adding extra information to the tree nodes, without changing the connectivity of the tree, that can be maintained quickly in a union operation and allows the find operations to return the correct values.)
Suppose that we want to make the union-find data structure partially persistent. We cannot use the path compression analysis, because that uses amortization, which does not work well with persistence. And we cannot directly use path copying persistence, because there are too many starting points for query paths (one for each different set element).
Instead of using fat nodes, it is possible to obtain a partially persistent structure by using union by size (without path compression), keeping only one parent pointer per node (non-persistently), and recording for each node a timestamp of the update that first changed its parent pointer from None to another parent. Describe how to perform a find query in this structure. Your query should take as arguments the element on which to perform the find, and the timestamp of a version of the structure to be queried.