Chapter 4 — Experimentation: An Introduction to the Scientific Method

Site Index

Each of chapters 2, 3, and 4 of Algorithms and Data Structures: The Science of Computing delves into one of computer science’s methods of inquiry by exploring some element of that method in detail. In chapter 4, the general method is empirical analysis, and the specific element is experimentation. Many students assume that “experiment” in computer science simply means casually running a program and seeing what happens. One of the most important lessons of this chapter is that in fact experiments are not trivial activities, that a convincing experiment actually requires careful design of experimental procedures and mathematical analysis of data.

Interacting Methods of Inquiry

While chapters 2, 3, and 4 nominally place each method of inquiry into its own chapter, they also illustrate that the methods are not really as easily separable as this organization suggests. Chapter 4 starts by wondering whether chapter 3’s theoretical analyses of algorithms’ performance are too abstract to capture real-world behavior, thereby motivating the need to test theoretical models empirically. Just as chapter 2 discussed algorithms as things that can be designed, and chapter 3 introduced mathematical tools for reasoning about algorithms, chapter 4 discusses the design of experiments, and introduces some simple mathematics for data analysis.

The inseparability of computer science’s methods of inquiry is a theme that should pervade courses based on Algorithms and Data Structures: The Science of Computing. Students should finish such courses (and readers should finish the book) appreciating that even if they most enjoy one method (e.g., some enjoy crafting programs, others enjoy proving theorems), they will be more successful in that method if they can also understand and use the others.

Classroom Activities

Demonstrating, or, even better, collectively designing and carrying out, an experiment is an ideal classroom activity to accompany this chapter. The goals of such an activity are to give students a concrete sense for what a good experiment is, to make sure they understand what the steps of an experiment and related terminology are (e.g., variables, experimental procedure, error sources, data, data analysis, etc.), and to bring out any questions or misconceptions students have about the chapter. Students should therefore be deeply involved in designing and conducting the experiment. Expect the activity to involve a lot of discussion between instructor and students, and to take a substantial amount of time (I like to use an hour to an hour and a half for it).

Experiments that I have used for this purpose include

• Derive a theoretical execution time for some algorithm while discussing chapter 3, and then design and conduct an experiment to test this result while discussing chapter 4. Simple algorithms for chapter 2’s robot (e.g., drawing a line, filling in a square) work well, because they are easy to analyze, and the robot has highly repeatable times for handling most of its messages (so measured execution times will be relatively noise-free). To do this experiment, I come to class with the original algorithm already coded into a program, but discuss with the students what data to collect, and where to add instrumentation code to collect that data. I also invite students’ suggestions concerning what problem sizes to run the program on, and how many times to run the program on each. Based on these discussions, I modify the program in class and run it in front of the students (if students also have computers in the classroom, they can run the experiment concurrently, providing an instant example of replication). Finally, I discuss with the students how to analyze the data the program produces, and what conclusions can be reached.
• Instructors who prefer to introduce experiments without the distractions of a computer can measure students executing algorithms by hand. For example, the grade-school pencil-and-paper multiplication algorithm takes Θ(n²) time to multiply two n-digit integers. A classroom experiment can verify this hypothesis. Students can be divided into groups, each group can be given numbers of different sizes to multiply, and group members can time each other doing the multiplications by hand. The average times for each n (number of digits) can then be plotted against n, or compared more quantitatively to n² (e.g., see if time/n² ratios are roughly constant). As in the prior example, involve students as much as possible in designing the experiment through class discussion prior to actually collecting data. Beware that such an experiment will have far more error sources than a computer-based experiment: people differ in how fast they do arithmetic by hand, some will make mistakes in their calculations (raising the interesting question of whether to include data on how long incorrect calculations take in subsequent analysis), etc.
• An experiment to test the hypothesis that the time it takes to communicate with an Internet host depends on the geographical distance to that host. Before class, the instructor should prepare a list of Internet hosts and their approximate distances from the school. During the class, round-trip communication times can be measured with a tool such as “ping.” (But beware that some firewalls block the packets sent by such tools, so this experiment may not be doable at all schools.) The instructor can make these measurements on a single computer whose display is projected for students to see, or students can do (some of) it on their own computers, if the classroom provides Internet access for student computers. As with the other experiments, students should contribute to defining the hypothesis, deciding what data to gather and how often, how to analyze it, and what conclusions to draw. Note that geographical distance alone does not completely explain Internet round-trip times, so this experiment will probably not find its hypothesis completely correct. I like this feature, since students need to learn that real experiments don’t always confirm their hypotheses, but others may find that explaining the outcome of this experiment detracts from demonstrating basic experimental concepts. Also note that students may enjoy this experiment more than the other examples, because this one makes a connection between computer science’s basic methods of inquiry and the “glamorous” area of networking.

Other Teaching Tips

Laboratory exercises in which students do experiments are particularly important ingredients in learning experimentation. Such exercises teach specific experimental techniques, data analyses, etc. This chapter is an excellent place for students to do their first formal computer science experiment, if they haven’t done one earlier. Of the laboratory exercises that accompany Algorithms and Data Structures: The Science of Computing, either the one entitled Introduction to Experimentation, or the one entitled Computer Science’s Methods of Inquiry, provide good first experiments.

This book makes a distinction between an experiment’s hypothesis and its prediction. A hypothesis is a general belief that an experiment tests (for example, “Insertion Sort runs in Θ(n²) time”), while a prediction is a specific expectation about the results of data analysis (for example, “dividing the running time of Insertion Sort by the square of the array size will yield a constant, even as array size varies”). This is, however, a subtle distinction, and many students have trouble understanding it. Instructors should be prepared to work with students to clarify it. Alternatively, concentrating on hypotheses when discussing experiments, and treating predictions as just the results one should see from data analysis if the data support the hypothesis, does little harm. For instance, the previous examples of a hypothesis and prediction about Insertion Sort could be presented as a formal hypothesis that Insertion Sort’s execution time is Θ(n²), followed by observing that hypotheses about execution time being Θ( f(n) ) can always be tested by dividing measured times by f(n) and looking for a constant, and that this rule can be applied to this hypothesis.

Further Reading

An illuminating explanation of pitfalls in timing Java programs appears in

S. Hansen, “Interpreting Java Program Runtimes,” Proceedings of the Thirty-Sixth SIGCSE Technical Symposium on Computer Science Education, Feb. 23 – 27, 2005 (SIGCSE Bulletin 37:1, Mar. 2005), pp. 36 – 40.

Copyright © 2005 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index