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

• There are quite a number of UNIX commands to time the execution of a program, among these time and timex. Read the man page for their usage. In some shells (e.g. csh), there is also a built-in version of time - read the man page for the shell for information on this. There are also corresponding C library routines called times, getrusage, and gettimeofday (which also have man pages). The availability may differ from machine to machine, though. It is part of the project to consider how to best time the execution of your programs.
• Computing random numbers is expensive.
• Make graphs of your results, e.g. using gnuplot.
• Run the program a suitable number of time for each input size and use the average running time. This should compensate fluctuations due to other processes.
• To perform several different executions, it is useful to have a script or meta-program that performs all the executions.
• Try to write programs that automatically checks if your algorithms and data structures work correctly.