Computer Science’s Methods of Inquiry

Site Index

Purpose

This exercise consolidates understanding of design, theoretical analysis, and experimentation by using all three to explore a simple problem.

Prerequisites

Understanding of chapters 2, 3, and 4 of Algorithms and Data Structures: The Science of Computing.

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, colorOfTile, heading) 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 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

Turn in a lab report describing your experiment. Format and submit this report as directed by your instructor.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 8, 2005 by Doug Baldwin

Site Index