Methods of Inquiry Lab

Site Index

This lab gives students a chance to practice some aspects of design, theory, and experimentation very early in a course. In practicing these things, students also begin to develop some appreciation for how the three methods of inquiry interact with one another.

This lab is associated with chapter 4 of Algorithms and Data Structures: The Science of Computing, because that is where the last of computer science’s methods of inquiry is introduced. In fact, however, the lab supplements all three of chapters 2, 3, and 4.

Design

This lab engages students in design by showing them two algorithms for moving robots diagonally, and asking students to translate those algorithms into Java. In doing this, the lab unfortunately does the most challenging and creative parts of design (discovering algorithms) for students, and leaves students to do the programming. Programming is an important aspect of design in computer science, but instructors should make sure that students don’t conclude that “design” is only programming by another name.

The reason this lab gives students the algorithms for moving diagonally is to ensure that every student has two distinct algorithms to use in the theoretical and experimental analyses. However, removing the algorithm descriptions from the lab handout and telling students to start by discovering two distinct ways of establishing the postconditions of moving diagonally would be a good variation on the lab for talented students.

Theory

Deriving expressions for the number of robot messages each algorithm sends is the theoretical analysis in this lab. This derivation requires analyzing loops, which isn’t formally introduced until chapter 9. However, the loops in both algorithms are simple enough that students should be able to analyze them on largely intuitive grounds. The example analysis in section 3.6 should help students understand what they need to do; supporting this reading with a similar example in the classroom should amply prepare all students to do the analyses in this lab.

Empirical Analysis

The part of this lab that deals with empirical analysis is the experiment. This experiment basically tests the theoretical analyses, by determining whether they accurately reflect the observable relative performances of the algorithms.

Hypothesis

Students form their own hypothesis for the experiment, based on their theoretical results. The student handout asks students to come up with as “specific” a hypothesis as possible, i.e., a hypothesis that is as precise as possible about the ratio (or other comparison) between the two algorithms’running times. A specific hypothesis leads to meaningful data analysis (see below), e.g., testing the measured data to see if they have the predicted ratio. Meaningful data analysis, in turn, helps students appreciate the role of data analysis in experiments generally.

Procedure

The default Robot constructor will position a robot in such a way that it can draw diagonals of between 1 and 4 steps. This is minimally enough to test the hypotheses students are likely to come up with in this lab, although some hypotheses will require longer diagonals, and in all cases longer diagonals provide more convincing tests of hypotheses. It is thus nice if students create non-default rooms, and place robots in a corner. Students can do this via the one-parameter constructor for rooms, and the four-parameter constructor for robots. See the Documentation on classes RobotRoom and Robot for details. In this manner, students can test their hypotheses on diagonals of up to 22 steps.

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

Data analysis for this experiment will generally be in two parts. The first is common to most experiments, namely averaging multiple measurements made of the dependent variable for each value of the independent variable, in order to get a “true” value of the dependent variable for that value of the independent variable. The second will use the “true” values computed in the first step to test the hypothesis. The details of this part of the data analysis will vary from student to student, as hypotheses vary. However, the analysis should always be as quantitative as possible. For example, if the hypothesis predicts a certain ratio between the algorithms’ execution times, then the data analysis might involve dividing the times for one algorithm by the times for the other, in order to see if the times have the predicted ratio.

The Report

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

1. A statement of the hypothesis the experiment tested.
2. 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.
3. 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.
4. 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.)
5. 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.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index