Data Structures · Graph representations and traversals
The fat-node method of partial persistence stores, in each field of each node, a…
Problem
The fat-node method of partial persistence stores, in each field of each node, a chronological list of (version, value) pairs. A field read at version \(v\) returns the value from the latest pair whose version is at most \(v\). A field write at version \(v\) appends a pair. Assume each list is an unsorted singly linked list, that versions are totally ordered integers, and that a new version is created by each update. Consider a linked structure of \(N\) nodes, each with a constant number of fields, subjected to \(U\) field writes spread arbitrarily across the nodes. Prove tight (\(\Theta\)) bounds, in terms of \(N\) and \(U\), on the worst-case time of a single field read and on the total extra space consumed by all version lists. Then redesign the per-field history as a balanced BST on version numbers and prove the resulting worst-case bounds on field read and field write.
Hint
An unsorted list forces a linear scan to find the latest version \(\le v\); the worst case concentrates writes on one field.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.
More Data Structures practice problems
- Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…Abstract data types, representation, and invariants
- A ring buffer (circular array) of fixed capacity C≥ 1 stores a sequence of at most C…Abstract data types, representation, and invariants
- Let L be the doubly linked list with values [10, 20, 30, 40, 50], and let I be a…Arrays, linked structures, stacks, queues, and amortization
- Consider BST deletion of a node zSearch trees and balanced trees
- Let T be a BST whose nodes contain only key, left, and right fields (no parent…Search trees and balanced trees
- Consider a hash table T of size m = 11 that resolves collisions by chainingHash tables and probabilistic performance
- Throw n balls independently and uniformly into n binsHash tables and probabilistic performance
- `Bubble-Down`(A,i,n) is specified as follows on a 1-based array that is a complete…Heaps, priority queues, and disjoint sets
- A duplicate minimum must sit on the min-stack, or one pop forgets the otherArrays, linked structures, stacks, queues, and amortization