1 - Introduction

Summary

The purpose of computing is insight, not numbers.

Richard Hamming, Numerical Methods for Scientists and Engineers

Some questions:

• You are a working programmer given a week to reimplement a data structure that supports client transactions, so that it runs efficiently when scaled up to a much larger client base. Where do you start?

• You are an algorithm engineer, building a code repository to hold fast implementations of dynamic multigraphs. You read papers describing asymptotic bounds for several approaches. Which ones do you implement?

• You are an operations research consultant, hired to solve a highly constrained facility location problem. You could build the solver from scratch or buy optimization software and tune it for the application. How do you decide?

• You are a Ph.D. student who just discovered a new approximation algorithm for graph coloring that will make your career. But you're stuck on the average-case analysis. Is the theorem true? If so, how can you prove it?

• You are the adviser to that Ph.D. student, and you are skeptical that the new algorithm can compete with state-of-the-art graph coloring algorithms. How do you find out?

One good way to answer all these questions is: run experiments to gain insight.

This book is about experimental algorithmics, which is the study of algorithms and their performance by experimental means. We interpret the word algorithm very broadly, to include algorithms and data structures, as well as their implementations in source code and machine code.