Department of Computer Science Aarhus University Department of Comptuer Science Faculty of Science

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:

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?