Catherine McGeoch, Amherst College, USA

Experimental Methods for Algorithm Analysis
Algorithm analysis is the task of predicting how well a given algorithm will perform in a given scenario. Analysis has traditionally been carried out using purely theoretical tools: abstract models of computation, worst-case (or perhaps average-case) assumptions about inputs, and asymptotic results. This approach produces deep new insights about the nature of computation, and -- of course -- many new and efficient algorithms. However, since the analysis model is necessarily abstract, theoretical results usually do not yield predictions that are specific and precise enough to be useful to practitioners: how does an $O(n^2 m \log^2 n)$ worst case bound translate to computation time in practice?

The practitioner, of course, can always implement an algorithm, run it on a collection of instances, and measure its performance. But the results may be of little use to other practitioners: My TSP implementation takes 2.3 hours to find a tour of cost 46.99 on my application; how well will it perform on your application?

These lectures discuss methods for using experiments to produce algorithm analyses that are more general than those typically found in empirical tests, and more environment-specific than those available through theoretical approaches. We consider broad methodological questions as well as tools and techniques most appropriate to these kinds of problems.

Lecture 1 will present an overview of the main questions faced by the algorithm experimenters: What should I measure? What input classes should I examine? What kind of questions should I ask? We will look at case studies as well as articles presenting commentaries on these questions.

Lecture 2 will discuss statistical and data analysis tools that are most appropriate to problems in algorithm analysis, with emphasis on graphical and exploratory methods. Tools and techniques for fitting (and bounding) functions to data will be highlighted. The lecture will also show how variance reduction techniques can be applied to problems in algorithm analysis.

Lecture 3 will consider practical tips for building a good experimental environment for research on algorithms. Seemingly small issues such as file formats, interfaces, and record-keeping will be considered. The lecture will finish with a discussion of how to present results, and a survey of Internet resources for experimenters.

References
Jon L. Bentley, Tools for Experimentation on Algorithms, CMU Computer Science: A 25th Anniversary Commemorative, (R. F. Rashid, ed.), ACM Press, New York , 1991.

Camil Demetrescu and Guiseppe F. Italiano, What do we learn from experimental algorithmics?

M. Coffin and M. J. Saltzman, Statistical analysis of computational tests of algorithms and heuristics, INFORMS Journal on Computing, 12, no. 1, pp 24-44, 2000.

David S. Johnson, A Theoretician's Guide to Experimental Analysis of Algorithms, in Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenge. Michael H. Goldwasser, David S. Johnson, and Catherine C. McGeoch, Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 59, American Mathematical Society, 2002.

Catherine C. McGeoch, Analyzing algorithms by simulation: Variance Reduction techniques and simulation speedups,' ACM Computing Surveys, 245, no 2, pp 195-212, 1992.

C. C. McGeoch, P. Sanders, R. Fleischer, P. Cohen, and D. Precup, Searching for Big-Oh in the data: Inferring asymptotic complexity from experiments, in Experimental Algorithmics, the State of the Art, R. Fleischer, B. Moret, and E. M. Schmidt, eds., Springer LNCS 2547, 2002.