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 that is due Friday December 18. The report should document 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:
- 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 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.