Exercises
- Consider the data structures covered in this and earlier courses. Which can be made partially persistent using the node-copying method from [DSST89]?
- Try the method from [DSST89] on a singly-linked list. The list must be kept sorted and there is one access pointer (to the first element in the list). Insert the elements (in that order): 1, 5, 9, 2, 3, 4, 8, 7, 6. Then delete: 5, 4, 3, 2, 1, 7, 8, 9, 6. Change version after each update (19 versions in total). Assume that there is one extra pointer. We will not need copy or inverse pointers. [We will not necessarily cover all of this in class.]
- Assume we have a singly-linked list of length n. We now repeat indefinitely: change to new version and make a change in the last element of the list. How often is the first element of the list copied using the method from [DSST89]? Assume that there is one extra pointer.
- Show that if there are fewer extra pointer fields than the number of inverse pointers, then the method from [DSST89] may use time which is not amortized constant per update.
- Again without copy or inverse pointers and just one extra field, try working with binary trees. From an empty tree, insert E, C, M, O, A, I, G, K, J (the ordering is lexicographic) and then delete M, E, A. Change version after each insertion or deletion. When deleting a key in a node with two nonempty children, physically delete the node containing the largest key smaller than the key to be deleted.
- Sketch an example where the copy pointer is needed.
- Sketch an example where inverse pointers are needed.