Advanced Algorithms - Data Structures (Fall 2007)

Project 3 - van Emde Boas Trees

The topic of this project is to compare the practical performance of van Emde Boas Trees with the priority queue implementations from Project 1 and with Red-Black search trees.

The project should be done in groups of 2-3 people.

The project consists of the following tasks:

1. Implement van Emde Boas trees based on the description in the note van Emde Boas trees (Gudmund S. Frandsen). As a minimum the following opeartions should be supported: FindMin, Insert, DeleteMin, Delete, PredecessorSearch
2. Design and perform experiments where you compare a van Emde Boas tree based priority queue with the priority queues from Project 1.
3. Design and perform experiments where you compare a van Emde Boas based search tree with red-black trees, using the implementation from Chapter 13 of Robert Sedgewick's book "Algorithms in C++, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching)" - the code is available at Robert Sedgewick's homepage.

Implementations should be done in C or C++. Elements stored should be 24 bit integers.

The project should be documented in a report that is due Friday December 21. The report should be send by email to gerth@cs.au.dk. 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.