Advanced Data Structures (Q1+Q2, 2015) - Projects
During the course you must handin three projects. The default
projects are projects 1-3 below. These are all implementation
projects and should be done in groups of 2-3 people. The projects
should be documented in reports describing your theoretical
considerations, implementation, experiment design and present your
experimental results. The evaluation of the reports and implementation
will be part of the final grade.
Alternatively, one or two (but not all three) of the projects 1-3 can
be replaced by any of the theory projects 4-6 below. Theory
projects must be documented by individual reports, i.e. no
group reports (you can discuss the theory projects in groups, but the
report must be indivual).
Please a.s.a.p. send the names of the
people in your group
to gerth@cs.au.dk.
Hints for implementation projects
-
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 times 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.
Project 1 (Implementation)
The topic of this project is to compare the practical performance of
Fibonacci heaps and binary heaps.
The project consists of the following tasks:
- Implement
-
the Fibonnacci
Heaps of Fredman and Tarjan,
- 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.
- Argue about the worst-case (as opposed to amortized)
time bounds for each of the operations
of Fibonnacci Heaps and binary heaps.
- Design and perform experiments where you try to measure the
running time and number of comparisons of the operations for both
priority queue implementations.
- 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.
- Describe families of graphs where Dijkstra's algorithm performs
many respectively few DecreaseKey operations.
- 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. The report should document your
theoretical considerations, implementation, experiment design and
present your experimental results.
Implementations should preferably be done in C or C++.
Project 2 (Implementation)
In this project you should select one of the below projects.
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:
- 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
- Design and perform experiments where you compare a van Emde Boas
tree based priority queue with the priority queues from Project 1.
- 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 preferably 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:
- Implement some of the approaches covered in the lecture on
"Discrete Range Searching" using space O(nlog n) words
and O(n) words.
- 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).
- (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 preferably be done in C or C++. Elements stored should
be integers.