Advanced Data Structures - Project 2

In the second project you should select one of the below projects. The project should be documented in a report that describes your theoretical considerations, implementation, experiment design and present your experimental results. The project should be done in groups of 2-3 people.

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

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

Range Minimum Queries

The topic of this project is the trade-off between the space usage and query time of different range minimum queries.

The project consists of the following tasks:

  1. Implement some of the approaches covered in the lecture on "Discrete Range Searching" using space O(nlog n) words and O(n) words.
  2. Measure the the query time and the total space usage of your data structures (e.g. by keeing simple counters for the total space allocated).
  3. (Optional) Implement and experiment with some of the ideas from the paper by Johannes Fischer: Optimal Succinctness for Range Minimum Queries, LATIN 2010: 158-16. This structure achieves 2n+o(n) bits and O(1) query time. What is the overhead in the o(n) term?

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