Lab 3 — Computer Science’s Methods of Inquiry

Purpose

Prerequisites

Background

The problem that this exercise explores involves making the robots introduced in chapter 2 of Algorithms and Data Structures: The Science of Computing move backwards.

Robots

The robots are available through a Java class named Robot (and a supporting class named RobotRoom). Programs that use these classes need to include two Java files: Robot.java and RobotRoom.java. The “Final Details” section of this document explains how to find these files and their documentation.

Any Java source file that refers to the Robot or RobotRoom classes should “import” those classes, via the statement

    import geneseo.cs.sc.*;

at the beginning of the file.

Moving Backwards

The robots described above move forward one tile in response to a move message, and clients who want a robot to move more than one tile forward can send multiple move messages to do so. There is no analogous way of making a robot move backwards. There are (at least) two approaches to extending robots so they can move backwards. In an approach directly analogous to the existing move, one could define a moveBack message that causes a robot to move one tile backwards; clients who want to move more than one tile backwards would send multiple moveBack messages. In a more general approach, one would define a travelBack message that takes a distance as a parameter, and makes a robot move that many tiles backwards; clients who wanted a robot to move one tile backwards would send a travelBack message with parameter 1.

In both cases, preconditions for moving backwards are that the tile(s) the robot needs to move onto are unobstructed. Postconditions are that the robot is facing in its original direction, and that it is the requested number of tiles behind its original tile (“behind” being defined relative to its original heading and position).

Given these pre- and postconditions, the basic moveBack algorithm is to turn the robot 180 degrees, move one tile, and then turn 180 degrees again. The basic travelBack algorithm with parameter n is to turn 180 degrees, move n times, and then turn 180 degrees.

Exercise

The exercise involves applying each of computer science’s methods of inquiry to the the problem of moving n tiles backwards, using the two approaches outlined in the “Background” section.

Design

The algorithm explanations in the “Background” section capture much of the insight behind designing algorithms for moving backwards. (Which is unfortunate, because insight is the hardest part of design. But it’s important for the rest of the lab that you have two measurably different ways to move backwards, so I needed to spell out the algorithms in relatively high detail.) However, the explanations don’t address the details of implementing either algorithm. Thus the first task is to write, in Java, a subclass of Robot that handles the moveBack and travelBack messages described above. Then write a main method that demonstrates two ways of moving n tiles backwards — sending n moveBack messages in one case, sending one travelBack message with parameter n in the other.

Theory

The second task is to derive mathematical expressions for the number of primitive Robot messages (move, turnLeft, turnRight, paint, okToMove, colorOfTile, heading) that each of the strategies for moving n tiles backwards sends, in terms of n.

Empirical Analysis

Finally, using the expressions for number of primitive Robot messages in terms of n, form a hypothesis about how the execution times of the two strategies will relate to each other. Be as specific as possible (e.g., it is better to say “the first approach will take ten times longer than the second” than to just say “the first approach will be slower than the second”). Then, design and conduct an experiment to test this hypothesis.

While planning the experiment, keep in mind the elements of good experiment design discussed in chapter 4 of Algorithms and Data Structures: The Science of Computing. Some issues that may be particularly relevant in this experiment include…

• Variables. Think consciously about what the independent and dependent variables are for this experiment, and how to measure them. Also think about how to make the independent variable(s) take on the largest possible range of values.
• Data Analysis. Almost every experiment should take several measurements of the dependent variable(s) for each value of the independent variable(s), and this experiment is no exception. Part of the data analysis will therefore be averaging the individual measurements for each value of the independent variable to get the corresponding “true” value of the dependent variable. But data analysis also needs to test the specific hypothesis you started with, and exactly how to do this will depend on the hypothesis. Look at your hypothesis, and try to devise a simple but quantitative way to determine whether your data are consistent with it.
• The Conclusion. The central conclusion from this experiment will probably be simple — either the data support the hypothesis, or they don’t. However, the conclusion (like many experiments’ conclusions) should not only say whether or not the data support the hypothesis, but should also mention additional information that the experiment revealed. For example, the conclusion may be able to mention observations about the apparent time to send a single robot message, may be able to discuss new hypotheses suggested by the experiment’s data, etc.

Final Details

The Robot Class

Both Robot.java and RobotRoom.java can be downloaded from the Web.

Documentation on both classes is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

This lab is due on Monday, February 7. Turn in a lab report describing your experiment. This report should discuss the following:

• The hypothesis the experiment tests, including the theoretical analysis leading to it.
• The experimental procedure you used to test the hypothesis. Much of the experimental procedure can be described by attaching a printout of your program, and then refering the reader to this printout at relevant places in the prose report. (But there will also be elements of the procedure that aren’t obvious just from the code, e.g., what values of the independent variable you tested, how many measurements you made on each, etc., so some prose will still be necessary.) This is also a good place to say what results you expect to see from the experiment (i.e., the prediction).
• All the data you collected.
• How you analyzed the data, and the results of that analysis.
• The conclusions you reached, including the reasons you reached them.

I would expect that you can cover these things in about 2 pages of text, not counting the program printout. However, I do not have hard and fast limits on how long the report has to be — the real requirement is that it say everything a reader needs to know in order to determine what your results are and whether they are believable, without using more text than necessary to say those things.

Portions copyright © 2004. Charles River Media. All rights reserved.

Revised Jan. 30, 2005