Project 3 (Honours version)
Note: The project reports should be done individually.
Fully retroactive queues
Prove that fully retroactive queues must require time at least time Ω(log m/loglog m) on a RAM. Hint: give a reduction from the parity problem considered in Project 2 to the fully retroactive queue problem ([Fredman & Saks, STOC 1989]).
Array initialization
Describe a data structure supporting the following three operations in worst-case constant time:
- Init(n) create a "list" L of length n with all entries set to nil.
- Set(i,v) set the ith entry of L to v.
- Get(i) return the ith entry of L.
The operations may use a procedure alloc(n) that in worst-case constant time returns an uninitialized array of length n, where each cell contains O(log n) bits, i.e., all entries of the allocated array contain random information.
Functional lists with index lookup
Describe a (strict) functional data structure supporting the operations push(x), pop(), and lookup(d), i.e. a functional stack supporting the lookup of the dth element. A normal list will support the operations in time O(1), O(1) and O(d) time respectively, whereas a balanced tree will achieve O(log n) time for all three operations, where n is the size of the list. Can you achieve the best of both worlds?