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
Multi-Dimensional Point Sets .
- For the usage patterns in a given
application (for example
shortest-path 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
- 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
``self-verifying'' data structures described by Gonnet? (For example,
a self-verifying 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 multi-dimensional point
- Compare k-d tree implementations of multi-dimensional 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
- Develop a instance generators that capture aspects
of a real-world problem.
- Implement data structures for parallel and distributed systems.