Practice Problem Set 10 Solutions
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?
Solution: This structure would consist of a path of nodes, with pointers to the end of the path (for enqueue operations) and to the start of the path (for dequeue operations). Each enqueue operation would change the next-node pointer in the node at the end of the path, and this change would propagate back up through the path all the way to the start of the path. So the whole path would need to be copied, so that the pointer to the start of the path would see the updated state of the data structure. It works, but not well: every enqueue is very slow.
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\).)
Solution: Let's first suppose that \(x\) is a left child of \(y\), so that in the finger tree we can reach \(y\) by following the left parent pointer from \(x\). We need two new nodes \(x'\) and \(y'\) replacing \(x\) and \(y\) and having the same keys. The left child pointer, right child pointer, and (left or right) parent pointer of \(x'\) are set to the left child pointer of \(x\), to \(y'\), and to the (left or right) parent pointer of \(y\), respectively. The left child pointer and right child pointer of \(y'\) are set to the right child of \(x\) and right child of \(y\), respectively; \(y'\) does not have a pointer to a parent node (its parent node points to it, instead).
The case where \(x\) is a right child of \(y\) is the same after swapping left for right.
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.)
Solution: Store a pointer to the smallest element of each set in the root node of the set. When we merge two trees, compare their two smallest elements and keep the smaller of the two. In a find operation, follow and compress a path to the root as before but return the element pointed to by the root node rather than the root element itself.
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.
Solution:
def query(x,version): while timestamp(x) ≤ version: x = parent(x) return x