Advanced Algorithms - Data Structures (Fall 2005)

Project 1 - Priority Queues

The topic of this project is to compare the practical performance of Fibonacci heaps and binary heaps.

The project should be done in groups of 2-3 people. Please a.s.a.p. send the names of the people in your group to gerth@cs.au.dk.

The project consists of the following tasks:

  1. Implement
    1. the Fibonnacci Heaps of Fredman and Tarjan,
    2. the binary heaps of Williams (Algorithm 232, CACM 21(4), 1964).
    As a minimum the following opeartions should be supported: MakeHeap, FindMin, Insert, DeleteMin, and DecreaseKey.
  2. Argue about the worst-case (as opposed to amortized) time bounds for each of the operations of Fibonnacci Heaps and binary heaps.
  3. Design and perform experiments where you try to measure the running time of the operations for both priority queue implementations.
  4. Implement Dijkstra's algorithm for the single-source shortest path problem for a weighted graph with non-negative edge-weigths, such that is can switch between the two priority queue implementations.
  5. Describe families of graphs where Dijkstra's algorithm performs many respectively few DecreaseKey operations.
  6. Perform experiments on your implementation of Dijksta's algorithm - in particular, try to observe if the version using Fibonacci heaps achieves an improved performance because of the amortized O(1) time DecreaseKey operation.

The project should be documented in a report that is due Wednesday November 2, 14.15, 2005. The report should document your theoretical considerations, implementation, experiment design and present your experimental results.

Implementations should be done in C or C++.

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

Hints


This page is maintained by Gerth Stølting Brodal <gerth@cs.au.dk>