Experiments for Algorithm Engineering Jon Bentley Bell Labs Lucent Technologies We'll start with a tiny program for finding exact solutions to Traveling Salesman Problems: it takes only a few dozen lines of code to enumerate all n! permutations and choose the shortest. We'll then engineer the algorithm to improve its run time, conducting experiments all the way to understand its performance. Along the way, we'll see a variety of experiments and tools that support them.