Instructor Notes

Introduction to Experimentation Lab

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)

Site Index

These notes describe the lab exercise entitled “Introduction to Experimentation”.

This lab requires students to design and conduct a simple experiment, thereby providing direct experience with the experimental process. When first introduced to the scientific method, many students don’t appreciate the differences between a well-planned experiment and haphazard data collection. This lab exercise can help those students begin to see that doing a good experiment is harder than they expected, and correspondingly merits more careful attention than they thought.

The Experiment

There are many acceptable experiments that students could do for this exercise, and instructors should not predetermine one “right” one. However, all experiments should be sound applications of the scientific method. The following subsections discuss some issues in “sound application of the scientific method” that extend those suggested in the main lab document.

The Hypothesis

Part of this exercise requires students to form a hypothesis. Hypothesis formation is an essential part of the scientific method, so we feel that asking students to do it is an important part of this lab. However, the requirement is slightly artificial, in that there is no standard computer science theory from which to deduce a hypothesis (in contrast to cases in which the hypothesis comes from applying some sort of theoretical reasoning to a particular situation). Students will thus form their hypotheses on all sorts of grounds — personal intuition, beliefs that move appears faster in one situation or the other, etc. Some students may read the code in Robot.java to see how move works in the two cases, and form a hypothesis based on that reading. In many ways, this is the soundest approach of all to forming a hypothesis for this experiment, and should not be discouraged. (Although we would not universally encourage it either, as not all students will be able to find or decipher the appropriate parts of Robot.java.)

The Prediction

Students often have trouble distinguishing between a hypothesis and a prediction, and the difference is indeed subtle. The student directions for this lab briefly discuss the difference, and provide an example hypothesis and an example prediction for this experiment. To help students who still have trouble understanding the difference, emphasize the different levels of specificity: a hypothesis is a broad statement about an entire group (all move messages, in this lab), while a prediction is a specific statement about what is expected in a specific situation (e.g., when a particular program sends move messages to robots in particular configurations). The examples in the student directions can be used to illustrate these points.

Experimental Procedure

A typical experiment might follow the prediction suggested in the lab description (i.e., if one causes one robot to move unobstructed, and another to try to move while facing an obstruction, the unobstructed robot will take less time — or more, depending on the hypothesis — to handle the move message).

The experimental procedure corresponding to such a hypothesis is straightforward: create the two robots, send each move messages, and insert timing code as described in Section 4.7.2 of Algorithms and Data Structures: The Science of Computing around the statements that send the move messages. It is better to put the timing code around the statements that send the messages than to add timing code to the body of the move method, because the former avoids modifying (and thus perhaps introducing bugs in) the experimental subject. Students should time both forms of move multiple times (3 to 5 is probably sufficient in this experiment), being careful that the unobstructed robot doesn’t move so far that it becomes obstructed. If the student believes that factors such as heading or tile color might affect time, he or she should conduct versions of this experiment that test multiple combinations of such factors (depending on the number of factors, it might not be feasible to test all possible combinations). All such factors not identified as relevant to time in the hypothesis or prediction should be kept constant between measurements.

In order to minimize the likelihood of garbage collection, students should use a small number of objects (e.g., 1 or 2), and should create all of them once, at the beginning of the program. Code such as the following should be avoided at all costs:

    // In some loop...
    Robot r = new Robot();
	 ...
	 // end of loop
Such code produces one piece of garbage on each iteration of the loop, ensuring garbage collection if the loop repeats often enough.

Data Analysis

There should be no more than one clock “tick” variation between time measurements for the same values of the independent variable(s). If an experiment yields data with about this level of variability, then it is sufficient to simply average the times measured for each form of move message (i.e., each combination of values of the independent variables), to get “true” times for that form of move. Directly comparing these times then tests the prediction.

If an experiment produces highly variable data, and the variability is not due to some correctable error in the experiment, then students can average a large number of measurements for each form of move, and calculate standard errors to estimate the error in each average. Students should base their conclusions on an informal analysis of the standard errors, e.g., whether the lowest plausible value for one time (taking standard error into account) is greater than the highest plausible value for the other. More sophisticated statistical analyses (e.g., confidence intervals) are usually beyond the scope of this course. Beware that the accuracy of standard error as an estimate of actual error rests on certain assumptions about the statistical properties of the raw data, with standard error becoming more reliable as the number of raw data items increases. We therefore prefer not to use standard error unless we have at least a few tens of measurements (e.g., 20 or more).

The Report

We ask our students to write lab reports that contain the following:

  1. A statement of the hypothesis the experiment tested.
  2. A statement of the prediction.
  3. An explanation of experimental procedure. A printout of any code written for the experiment can provide much (but seldom all) of the necessary information, shortening the prose part of the report.
  4. All of the data collected. It is important to show raw data so that readers can check the data analysis and conclusions, make their own judgments about error levels, etc. Data are often clearest when shown in a table.
  5. A description of, and the results from, data analysis. In this experiment, this can simply consist of a few additional rows or columns in the table of raw data. (In which case, using a spreadsheet program to build the table, and attaching a printout of the result to the lab report, can save lots of work.)
  6. A statement of the conclusion(s). This should at least state whether the experiment does or does not support the initial hypothesis, and why. It is also an opportunity to comment on or speculate about other things that occur to the student during the experiment (for example, do the data suggest new hypotheses or predictions? Are there further experiments that now seem worth doing? Improvements to the present one?)

One and a half to two pages (exclusive of code) is often sufficient to describe an experiment such as this one.

A Note on Clock Resolution

While Java’s System.currentTimeMillis method always measure time in units of milliseconds, it need not have a resolution of 1 millisecond in all Java implementations. In other words, the clock may only “tick” every couple of milliseconds, as long as the value returned by System.currentTimeMillis changes by the appropriate number of milliseconds at each tick. For example, we have seen some Java implementations in which the clock ticks every millisecond, and others in which it ticks approximately every 10 milliseconds. Thus, do not be surprised if students cannot measure a change in time as small as 1 millisecond.

The following code can be run to find the resolution of System.currentTimeMillis in a particular Java implementation:

    long start = System.currentTimeMillis();
    while ( System.currentTimeMillis() == start ) { }
    long end = System.currentTimeMillis();
    System.out.println( "Clock resolution is " + ( end - start ) );

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index