Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
The Robot library class implements the simulated robots described
in Chapter 2 of Algorithms and Data Structures: The Science of Computing.
The RobotRoom class is a supporting class for Robot,
providing the “rooms” in
which robots exist. Any program that uses one of these classes must include
both.
The Robot class facilitates a number of exercises
in, and demonstrations
of, concepts from Parts I and II of Algorithms and Data Structures: The
Science of Computing. In this respect, the class is an alternative to
the LineDrawing class. Robots
provide better step-by-step animation as algorithms execute than do line drawings,
and
are
specifically
designed to be easy to do timing
experiments with. On the other hand, line drawings
support richer graphics, which leads to more interesting
theorems
that can be proved about line drawing algorithms. Robots are thus the best choice
for exercises in which students should be able to see their algorithms executing
literally step by step, or for simple experiments.
Robots illustrate a number of object oriented programming concepts. Simply
creating one or more Robot objects
and sending them messages to do simple tasks illustrates creation
and
use
of
objects. Defining subclasses of Robot with methods for tasks
other than those provided by Robot (e.g., coloring a line instead
of a single tile) demonstrates the use of subclasses to extend the functionality
of their superclass. These demonstrations readily expand to include such
features as method overriding (have the subclass redefine one of the standard
robot
messages)
or polymorphism
(define two or more subclasses that handle the same message(s) in different
ways), etc.
Simple robot algorithms can illustrate any of the standard control structures. There are also a number of natural recursive robot algorithms, ranging from tail recursions for moving more than one tile or drawing a line (see the examples in Chapter 6 of Algorithms and Data Structures: The Science of Computing), to complex recursions for, e.g., maze following.
Correctness proofs and performance analyses of the above algorithms illustrate theoretical analysis of various control structures and recursions. Experimental confirmation of the theoretical results provides a number of introductory examples of experimentation.
Robot objects are visual and animated: the objects appear as
visible markers on the computer screen, and move, turn, color parts of the
screen, etc. in response to messages. This helps students understand and debug
robot algorithms, because the student can literally see the effects caused
by a program. By default, robots move slowly enough that students can see individual
steps happen. Programs can, however, set the speed with which a robot moves,
for example to make long algorithms run in a reasonable amount of time. In
all cases, the speed with which a robot acts is controlled by code in the Robot class,
which makes experimental timing data from robots easier to measure
and less
noisy than data
from other experiments.
The RobotRoom class represents the rooms in which robots exist.
Pragmatically,
RobotRoom objects also provide the windows in which robots
appear
on a monitor.
Students will hardly ever do more with RobotRoom objects than
create them. In simple cases, they don’t even need to do that, as one
of the Robot constructors automatically creates a room for the robot to
exist in.
Files named Robot.java and RobotRoom.java,
which define the Robot and RobotRoom classes, can be
downloaded from the Web. Documentation for
both
classes
is
also available on
the Web.
Both Robot.java and RobotRoom.java need to be present in any program that uses robots.
The Robot and RobotRoom classes are part of the geneseo.cs.sc package.
Source files that use the classes thus usually import them.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin