2015-05-12

A Theoretician's Guide to the Experimental Analysis of Algorithms

Authors

David S. Johnson

Abstract

This paper presents an informal discussion of issues that arise when one attempts to analyze algorithms experimentally. It is based on lessons learned by the author over the course of more than a decade of experimentation, survey paper writing, refereeing, and lively discussions with other experimentalists. Although written from the perspective of a theoretical computer scientist, it is intended to be of use to researchers from all fields who want to study algorithms experimentally. It has two goals: first, to provide a useful guide to new experimentalists about how such work can best be performed and written up, and second, to challenge current researchers to think about whether their own work might be improved from a scientific point of view. With the latter purpose in mind, the author hopes that at least a few of his recommendations will be considered controversial.

Discussion Notes

• The author made a strong push for a high academic quality of research reporting which was interesting to hear from a person in industry (working at the AT&T research lab).
• Talked about the various pitfalls, suggestions, and pet peeves. In particular, the advice related to our experiences running experiments, preparing data and writing reports in our 481 Parallel Systems course.
• Noted that the paper would have been a helpful initial reading for other courses at university and as an introduction to academic writing.
• The paper will help us evaluate and gain insight into the choices made in the creation of papers used for future discussions.