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

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 three 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 stored in the subtree ≤x. The tasks of the project are to:

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:

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:

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