Data Structures and Algorithms Experimental Design

Designing Experiments

Designing a good experiment is not a trivial task: it needs some thought and care if the results of your work are going to lead to valid conclusions. While there are many variations of good strategies, the following basic steps will generally lead to a good procedure:
1. Form a hypothesis which your experiment(s) will test,
2. Design some experiments to test this hypothesis,
3. Run the experiments and collect the data,
• Transform your raw experimental data into a form which permits readily verifying or disproving the hypothesis,
• Estimate the experimental error in the original data and transformed data,
• Compare the transformed data with expectations produced by the hypothesis.
5. If the experimental data and expected results are in accord (within the experiment's error limits), then you have a basis for claiming the original hypothesis to be true.
6. If there is a discrepancy, you have a number of strategies:
• Analyse the experiments for sources of error,
• Repeat the experiments to confirm the results (not usually very profitable for computer based experiments!)
• Re-design the experiments or
• Form a new hypothesis.
Of course, if you are doing original research (that is, you are testing some new hypothesis for the first time), then you now need to form alternative hypotheses and see whether the experimental data would match them also and repeat the experiments (or formulate new ones) to ensure that you can reproduce the original results. This cycle is potentially never-ending!

However, for the experiments you will need to do in this course, the results are well-known and one 'pass' through this process should suffice!

Rules

There are a few very important rules:
1. You must report all experimental results, unless they are clearly wrong (eg your program had an error).
2. You may not reject any measurement unless you can provide an iron-clad argument to justify its rejection.

An example of an acceptable reason for rejecting or ignoring a result is:

The computer's timer has a minimum resolution of 10ms, so all runs with times less than 1s were ignored because they could have had errors >1%.
Of course, a really careful experimenter would not discount these results either, but confirm that they also matched the hypothesis - making allowance for the known error. However, in the interests of efficiency, this level of precision will not be expected here!

Reporting results

It is usual to transform your results to some form which makes it easy to verify that they conform to the hypothesis. The most common strategy is linearisation - plotting results on a graph with axes designed to produce a straight line. Another good strategy is normalisation - reduction of all results to a constant value. This normalisation strategy is a good one to employ here: assume that you are verifying the time complexity of quicksort. This is usually a O(nlogn) algorithm.
• Your hypothesis is that quicksort takes n logn time, or more formally:
T(n) <= c n log n
where T(n) is the time to sort n items and c is a constant.
• So time a series of sorts of increasingly larger collections of items.
• Divide the times by nlogn. If you have a set of constants, c +/- some suitably small variation, then the running time may be expressed as:
T(n) = c n log n