5 - The Toolbox

Summary

Write your workhorse program well; instrument your program; your experimental results form a database: treat it with respect; keep a kit full of sharp tools.

Jon Louis Bentley, Ten Commandments for Experiments on Algorithms

They say the workman is only as good as his tools; in experimental algorithmics the workman must often build his tools.

The test environment is the collection of programs and files assembled together to support computational experiments on algorithms. This collection includes test programs that implement the algorithms of interest, code to generate input instances and files containing instances; scripts to control and document tests, tools for measuring performance, and data analysis software.

This chapter presents tips for assembling and building these components to create a reliable, efficient, and flexible test environment. We start with a survey of resources available to the experimenter. Section 5.1 surveys aspects of test program design, and Section 5.2 presents a cookbook of methods for generating random numbers and combinatorial objects to use as test inputs or inside randomized algorithms.

Most algorithm researchers prefer to work in Unix-style operating systems, which provide excellent tools for conducting experiments, including:

• Utilities such as time and gprof for measuring elapsed and CPU times.

• Shell scripts and makefiles. Shell scripting makes it easy to automate batches of tests, and makefiles make it easy to mix and match compilation units. Scripts and make files also create a document trail that records the history of an experimental project.

• […]