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

Project 2 - 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 (lecture note by 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 e.g. 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 describes 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.