Project 3

In the final project you should select one of the below possible projects. Alternatively, if you can define another project related to the course content, you are also welcome to do so. If you wish to do another project than one of the topics listed below, this must be approved before starting the project. Please send the suggestion for an alternative project to gerth@cs.au.dk for approval.

The project should be done in groups of 2-3 people. The project should be documented in a report describing your theoretical considerations, implementation, experiment design and present your experimental results.

Note: The evaluation of the report and implementation will be part of the final grade.

Retroactive search tree

In this project retroactive search trees should be implemented - both partially and fully retroactive search trees. The update operations to the (non-retroactive) search tree should be Insert(x) and Delete(x), and the query operation should be Pred(x) that returns the largest element ≤x stored in the tree. The tasks of the project are to:

• Define an appropriate interface to a partially and a fully retroactive search tree.
• Implement a search tree, a partially retroactive search tree, and a fully retroactive search tree [DIL, Section 4].
• Test if your retroactive solutions are correct by comparing them with simple rollback solutions.
• Compare experimentally the performance of the different data structures.
• Compare experimentally the performance of the fully retroactive search tree with a simple rollback solution. What are the thresholds where the complicated solution is superior to the rollback solution?

Unified dictionaries

In this project the unified dictionary data structure from [BCDI07] should be implemented and compared with other dictionary data structures. The tasks of the project are to:

• Design a set of different experiments for the unified data structure of [BCDI07] with various distances to recently accessed elements.
• Implement the unified data structure from [BCDI07].
• Experimentally compare the performance of the unified data structure with the red-black trees from Project 2 and optionally also with splay trees.

Functional queues

In this project you should do an experimental study of a functional data structure. Implementations should be done in the lazy functional language Haskell (see www.haskell.org) using the ghc compiler. The tasks of the project are to:

• Setup a framework for repeatedly running and timing a Haskell program (does not need to be implemented in Haskell).
• Implement various queue implementations in Haskell:
  • Using a standard Haskell list as a queue.
  • Using a pair of lists (left-part,right-part) with an amortized O(1) time guarantee provided the same queue will never be the argument to repeated queue operations (i.e. expensive operations cannot be repeated).
  • Using O(1) lists with a worst-case guarantee of O(1) time per enqueue and dequeue operation (if executed strictly).
  • Using a pair of lists (left-part,right-part), exploiting the properties of lazy evaluation of list concatenation to guarantee amortized O(1) per queue operation.
• Design and perform experiments comparing the different implementations. The experiments should cover both the case where a queue is only used once as an argument to a queue operation (i.e. expensive operations cannot be repeated) and the case where queues can be used in the general way functional programming allows (i.e. the case where the same queue can be used as an argument an unlimited number of times and an expensive operation can be repeated arbitrarily often).

Note: Since Haskell is a lazy functional language, the timing experiments might not be as expected, since the functions called might actually never have been evaluated. To ensure that functions always get evaluated, ensure that you somehow output a result using the result of your computation.

Theoretical Project

Write a report answering each of the following questions.

1) Prefix parity/sum

Let A be an array of size n, where each A[i] is either 0 or 1. Describe a data structure that supports updating an entry of A to either 0 or 1, and the query sum₂(i) that returns (A[1]+A[2]+...+A[i]) mod 2, ie. decides if the sum of the first i entries of A is odd or even.

What is the best query time and update time you can achieve? A lower bound of Ω(log n/log log n) is known for the operations on the RAM ([Fredman & Saks, STOC 1989]).

Optional: Generalize the construction to return the sum A[1]+A[2]+...+A[i], ie. the number of entries equal one among the first i entries.

2) 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 1) to the fully retroactive queue problem (lower bound from [Fredman & Saks, STOC 1989]).

3) 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.

4) 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?

5) Maxiphobic heaps

In the description of maxiphobic heaps [Okasaki 2005, Section 3] it is stated:

Finally, note that "size" in maxiphobic heaps can be interpreted as either number of nodes or height of the tree. Either interpretation leads to a successful solution.

Describe and analyse a solution of maxiphobic heaps based on height.