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 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 ``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 sets.

• 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 implementation strategies.

• Develop a instance generators that capture aspects of a real-world problem.

• Implement data structures for parallel and distributed systems.