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 diagonally.

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 Diagonally

Within this exercise, moving a robot diagonally n tiles means establishing the postcondition that the robot is n tiles forward of the its initial position, and n tiles right of the its initial position. “Forward” and “right are both defined relative to the robot’s initial orientation. The robot should have that same orientation when it finishes moving diagonally. The diagram below illustrates these postconditions:

Assume as a precondition that there are no obstacles within n tiles forward and right of the robot.

At least two algorithms exist to move a robot diagonally under these definitions. One algorithm moves the robot n tiles forward, then n tiles to the right, as suggested here:

The other algorithm alternately moves the robot one tile right, then one tile in the original forward direction, then one right again, and so forth until the robot is n tiles forward and right of its original position:

Exercise

The exercise involves applying each of computer science’s methods of inquiry to the two algorithms for moving diagonally outlined in the “Background” section.

Design

The algorithm explanations in the “Background” section capture much of the insight behind designing algorithms to move a robot diagonally, but they don’t address the details of implementing either algorithm. Thus the first task is to write, in Java, a subclass of Robot that handles two “move diagonally” messages: one, perhaps named moveDiagonally1, is handled by the first algorithm, the other (perhaps named moveDiagonally2) is handled by the second algorithm. Both messages take n as a parameter. Write a main method that tests both ways of moving diagonally.

Theory

The second task is to derive mathematical expressions for the number of primitive Robot messages (move, turnLeft, turnRight, paint, okToMove) that each of the methods for moving diagonally 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 algorithms will relate to each other. Be as specific as possible (e.g., it is better to say “the first algorithm will take ten times longer than the second” than to just say “the first algorithm 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 variables 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

Turn in a short report describing your experiment and the work leading up to it. This report should include the analyses of the two “move diagonally” algorithms, a statement of the hypothesis formed from that analysis, a description of how you did the experiment, all the data collected and results from data analysis (be careful to include the original “raw” measurements as well as their averages), and the statement of conclusions. Attach a printout of the code you wrote to the report — this will make it much easier to describe how you did the experiment, because many of the details can be dealt with by simply saying “see the attached code” instead of having to describe them in prose in the body of the report. Not counting the printout, the report can probably be written in 1 1/2 to 2 pages.

In addition to concluding whether your hypothesis is supported or not, the conclusions in your report should also include a sentence or two about how you found design, theoretical analysis, and experimental analysis to interact in this lab — for example, did you find that they complemented each other, or did they interfere with each other? Was it clear when you were doing each, or did they seem to sort of merge together? Do you think there would be similar interactions when tackling other computing problems? And, of course, feel free to remark on anything else you found interesting about this exercise.

Copyright © 2004. Charles River Media. All rights reserved.

Revised Sep. 8, 2004