Experimental Algorithmics

Main Page
Research Projects
Relevant Links
Computer Science
NOTE: This set of pages is only maintained sporadically. Go instead to the web pages for the
Laboratory for High-Performance Algorithm Engineering and Computational Biology.

The last 20 years have seen enormous progress in the design of algorithms, but very little of it has been put into practice, even within academia; indeed, the gap between theory and practice has continously widened over these years. Moreover, many of the recently developed algorithms are very hard to characterize theoretically and, as initially described, suffer from very large running-time coefficients. Thus the algorithms and data structures community needs to return to implementations as the standard of value; we call such an approach Experimental Algorithmics.

Experimental Algorithmics studies algorithms and data structures by joining experimental studies with the more traditional theoretical analyses. Experimentation with algorithms and data structures is proving indispensable in the assessment of heuristics for hard problems, in the design of test cases, in the characterization of asymptotic behavior of complex algorithms, in the comparison of competing designs for tractable problems, in the formulation of new conjectures, and in the evaluation of optimization criteria in human-related activities. Experimentation is also the key to the transfer of research results from paper to production code, providing as it does a base of well-tested implementations.

My work has ranged over most of the areas listed above. I also initiated the new ACM Journal of Experimental Algorithmics, an archival on-line journal devoted to the area. I organized and chaired the recent 2nd Annual Symposium on Algorithm Engineering and Experiments (ALENEX00) and co-chaired the first Schloss Dagstuhl seminar on Experimental Algorithmics, which will be repeated in Fall 2002, and I am chairing the first Workshop on Algorithms in Bioinformatics (WABI 2001), which will bring together researchers in computational biology and algorithm engineering.

Current work includes large-scale experimentation (well over 4 years of CPU time!) in phylogeny reconstruction (with colleagues at U. Texas, CUNY, and Aventis), high-performance algorithm engineering and parallel computing for phylogeny reconstruction (the GRAPPA software suite -- see also the Access magazine feature article on it), sponsored by NSF under three grants, EIA-01-21377, EIA 01-13095, and DEB-01-20709, as well as another NSF-sponsored project, ITR 00-81404 (in collaboration with David Bader) to build a proof-of-concept library of basic graph and geometric algorithms for shared-memory parallel computers.

Computer Science Department
Farris Engineering Building
University of New Mexico, Albuquerque, NM 87131
Phone (505) 277-3112, FAX (505) 277-6927
Email: csinfo@cs.unm.edu