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\).)
Let \(T\) be a complete binary search tree on the seven numbers from 1 to 7. (Complete means here that there is one root node, two children of the root, and four grandchildren of the root.) Suppose we wish to answer the following queries: for a pair of real numbers \((x,y)\), find the nearest numbers in \(T\) to \(x\) and \(y\), and return the number of their lowest common ancestor. For instance, 1.3 and 2.8 would round to 1 and 3 respectively, and return lowest common ancestor 2.
Now interpret the query numbers \((x,y)\) as coordinates of points in the plane. Partition the plane into regions within which the answer to this rounded LCA query problem is constant, according to the locus method, and draw the resulting partition. (Your drawing should cover the region of the plane within which both coordinates are between 0 and 8.)
Define an adder to be a very simple data structure that stores a single number \(\Sigma\) (the sum of the numbers given to operations on this data structure, initially zero), with a single update operation update\((x)\) that adds \(x\) to \(\Sigma\), and a single query operation that returns \(\Sigma\).
Describe the API for a retroactive version of the adder data structure. You do not need to describe how to implement this API.
Describe (in English or pseudocode) how to use a retroactive data structure as a subroutine to implement the (non-retroactive) array prefix sum problem of Week 7, and use this implementation to conclude that a retroactive adder requires at least logarithmic time per operation. (Hint: maintain a retroactive sequence of operations that adds all the values in the current array.) How do the update and query operations from the prefix sum problem translate into your retroactive adder operations from part (a)?