Work Note 15, DM206, fall 2008

Exercises December 9

1. Consider the data structures covered in the course. Which can be made partially persistent using the node-copying method from [DSST89]?
2. 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 necessarily cover all of this in class.]
3. 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.
4. 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.