Data Structures · Abstract data types, representation, and invariants
Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…
Problem
Data Structures practice problemLet be a dynamic array of elements stored in a buffer of capacity , with the invariant and . The operation writes a new element in time if . If , allocates a new buffer of capacity , copies the existing elements, writes the new element, and deallocates the old buffer. The operation removes the last element in time if and, after the removal, if and , it allocates a new buffer of capacity , copies the remaining elements, and deallocates the old buffer.
Adopt the standard uniform-cost RAM model in which allocating or deallocating a buffer of capacity and copying elements each cost , and all other primitive steps cost . Starting from , , consider an arbitrary mixed sequence of successful and operations ( is never invoked on an empty array). Prove that the amortized cost of each operation is . You may use either the aggregate method or the accounting method; if you use accounting, state the credit invariant relating stored credits to and , and prove that the invariant is maintained and that every operation's actual cost is covered. Finally, exhibit a concrete infinite family of operation sequences showing that if shrinking were instead triggered whenever after (with new capacity ), then the amortized cost would no longer be .
Hint
HintThe shrink threshold, rather than the grow threshold, is what stops a single Truncate after a doubling from immediately reallocating.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
Create a free account to check your answer and see the solution. Create a free account.
More Data Structures practice problems
- 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
- The fat-node method of partial persistence stores, in each field of each node, a…Graph representations and traversals
- A duplicate minimum must sit on the min-stack, or one pop forgets the otherArrays, linked structures, stacks, queues, and amortization