The Fifth DIMACS Challenge

The Fifth DIMACS Challenge runs from November 1995 to Spring 1997. This year, the Challenge topics are Priority Queues and Dictionaries.

Useful Information

• The Challenge Workshop was held on October 28--30 at the DIMACS building on the campus of Rutgers University in Piscataway, NJ. A Workshop Schedule is available. At the workshop, Challenge participants presented talks describing their preliminary results. The workshop also featured talks by invited speakers on experimental methodology for algorithms and data structures. Thank you all for intriguing presentations and lively discussions! This page contains some follow-up information.

• Challenge Participants. At present we are developing specifications and support material for a set of core test instances with which participants can test their implementations. These specifications should be ready by the first half of January; they will contain previously-announced tests as well as a few new ones. Participants will be expected to carry out any new experiments and to prepare final papers for publication in the Proceedings. The tentative deadline for final papers is Late March. Please follow the MAA publication guidelines for authors as you prepare your papers!.

• Methodology Day Participants. Those of you who gave presentations on Methodology Day are warmly encouraged to prepare position papers for publication in the proceedings. We would especially like to build an annotated bibliography containing examples of good and excellent experimental research on algorithms. The deadline for submission of papers is Late March, but you can send bibliography comments and suggestions at any time before then.

Priority Queue Resources

• The (first round) core experiments for priority queues are available.

• The core experiment page describes several families of priority queue problem generators which are available at our anonymous ftp site. We encourage and expect participants to perform more extensive or detailed experiments relevant to their research projects, perhaps using these generators.

  NOTE In spring 2003 the above FTP site was re-located. You can now find the material here.

Dictionary Resources

• The (first round) core experiments for dictionaries are available.

• The core experiment page describes several families of priority queue problem generators, and instances from real applications, which are available at our anonymous ftp site (and other sites). We encourage and expect participants to perform more extensive or detailed experiments relevant to their research projects, perhaps using these generators.

  NOTE In spring 2003 the above FTP site was re-located. You can now find the material here.

Multidimensional Point Set Resources

So far, we have no contributions from implementers of multidimensional point sets. We will be glad to specify a core set of experiments for multidimensional point sets when we know more about what kind of point set data structures are being developed out there. We need to hear from you.

Other Useful Bits Of Information

• DIMACS Home Page The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) sponsors the Challenge.

• Call for Participation. A one-page blurb describing the Challenge.

• Some Project Ideas. A list of research project ideas that we thought of off the tops of our heads.

• Data Type Definitions and Specifications ( Postscript version). This document specifies the syntax and semantics of the abstract data typesg. You can get a LATEX document together with a macro file if you prefer. The document was last modified on 4 June 1996 . Changes are listed in the first section.

• LEDA Home Page. LEDA is a Libarary of Data Types and Algorithms, implemented in C++. The Challenge is designed to be compatabile with LEDA standards. You can also go directly to the anonymous ftp site.

• Useful Web Pages. Some interesting and useful pages for those interested in empirical research on data structures and algorithms.