Challenge Project Ideas
Here is a list of questions and suggestions
to stimulate project ideas. Of course, we
welcome other research projects related to Priority
Queues , Dictionaries and
MultiDimensional Point Sets .
 For the usage patterns in a given
application (for example
shortestpath algorithms or network flows), how well do the leading
priority queue implementations perform?
 Are the theoretically best hashing schemes useful in
practice? How much computation time is required to do the hash?
How can these hashing schemes be adapted to large keys and realistic
key properties?
 How much efficiency is lost in an implementation that supports
extra operations beyond those specified for the Challenge? What about
persistence, for example?
 How much efficiency is lost if you implement the
``selfverifying'' data structures described by Gonnet? (For example,
a selfverifying search tree monitors
internal consistency, guarding against the possibility of an
untrustworthy comparison function provided by the user.)
 Which flavor of balanced tree?
 Compare tiling strategies for multidimensional point
sets.
 Compare kd tree implementations of multidimensional point sets
to anything else.
 How much does cache size affect performance on RISC
architectures? What kinds of performance difference
is observed across RISC and CISC environments?

Extend random models of input. Develop instance generators with
parameters that separate performance of competing
implementation strategies.
 Develop a instance generators that capture aspects
of a realworld problem.
 Implement data structures for parallel and distributed systems.