Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
These notes discuss the laboratory exercise in which students design a Robot Treasure Hunt algorithm. This exercise draws on and reinforces materials from chapters 6 and 7 of Algorithms and Data Structures: The Science of Computing.
Because this exercise asks students to design, analyze, and implement a single algorithm, and because that algorithm differs from shorter algorithms in other labs more in its size than in its content, this exercise is well-suited for use as a homework assignment instead of as a closed lab exercise. Students can have supervised practice working with recursive algorithms while doing such labs as those on Elementary or Intermediate Recursion with Robots, or Intermediate Recursion with Line Drawings, and then have a chance to work more independently in this exercise. We often use this exercise as homework ourselves.
Many students have trouble seeing how to use recursion in this exercise. Often, the problem is not seeing how to recursively move a robot to the end of a path, but seeing how to bring it back afterwards. Thinking carefully about postconditions on the robot’s position can solve this problem, by drawing attention to where the robot is after recursively solving a small treasure hunt, and what needs to be done to put it where it should be after solving the larger treasure hunt that the small one is part of. Once students work through this thinking for one or two clues, they generally see how to think similarly about the others.
The correctness proof for this algorithm is long, but not unduly difficult. It is, however, best done by strong induction, which is covered, albeit not very prominently, in section 7.1 of Algorithms and Data Structures: The Science of Computing.
Depending on students’ background with Java, they may need more information on file I/O and exceptions than presented in this exercise’s student directions. The discussion there assumes that students have either seen these things before and need only a reminder of how to use them, or that they will receive additional information from the instructor.
Simple variations on this lab can be created by changing the mapping of colors
to clues, adding new kinds of clue (possibilities include forking three ways — left,
right, and forward; moving more than one tile in some direction before reading
the next clue; etc.), or deleting some kinds of clue. Note, however, that the
six kinds of clue in the current exercise use all the tile colors that the
RobotRoom constructor recognizes, so instructors who want
to add clues without removing any will have to find some way other than that
constructor to set up treasure hunts.
Changing the clues will require changing the sample treasure hunt files, or creating new ones from scratch. The student directions for this lab contain links to the sample treasure hunts on Charles River Media’s Web server. It should be easy for someone who wants to alter these treasure hunts to download them — they are plain text files, so most browsers should be able to fetch them and save them locally. Beware, however, that the larger treasure hunts involve very long room descriptions, and long room descriptions are not very readable. It may be easier to recreate large treasure hunts from scratch than to edit the samples, unless the changes are purely mechanical, such as changing tile colors.
A different variation on the exercise is to read
the sample treasure hunts directly over the Internet rather than from local
files. Writing a
program that uses the Internet in such a manner is usually exciting for students,
particularly if it is their first experience writing network programs. The
relevant network programming is easy in Java, using either the standard Java
library class URL, or the WebPage class developed
for
use with
Algorithms
and Data Structures: The Science of Computing. The latter is easier
for students, the former better preparation for working with standard Java
libraries.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 28, 2005 by Doug Baldwin