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 describe the lab exercise on Debugging. We discuss the philosophy behind the lab, points instructors may wish to make with the lab, and variations on it that instructors may wish to try.
Our goal in this lab is to get students to think systematically about the debugging process, and to get them to appreciate that the same theoretical tools that help them think systematically about abstract algorithms can help them debug. For most students, this represents a significant change in how they think about debugging, a change that a single lab will not fully achieve. This lab is a starting point for changed thinking, and its lessons should be reinforced as students debug later programs.
Because the reasoning people use while debugging is the important lesson of this lab, we ask our students to turn in a description of their reasoning as part of their solution to the lab. We encourage other instructors to do the same. Beware, however, that students often have trouble understanding that they need to describe a fairly lengthy, deep, thought process, not just describe what parts of the code were wrong.
The comments in BuggyRobot.java are deliberately a bit sparse. We find that given good comments, students will sometimes debug by simply making the code do what the comments say, without really trying to identify and isolate the things in the code that make it fail. This is a good lesson in the value of comments, but not really the lesson this lab is supposed to teach, so we made the comments sketchier in this file than we usually do.
This lab is an obvious opportunity to give students a quick tutorial on the debugger in their development environment, if they have not already learned to use it. We don’t include any such tutorial in the instructions to students, because debuggers differ between environments, and students may have learned to use one in an earlier course. However, we encourage instructors to either talk about debuggers prior to students doing this lab, or to hand out information on the local debugger along with the lab handout, if students have not already been exposed to debuggers.
The BuggyRobot class includes a large number of private “helper” methods
that the public methods invoke. Using such helpers is a good modular programming
technique, and
working with the code for this lab is a good way to expose students to it.
The helpers do, however, make the class as a whole more complicated than it
would
have been without them, and students may therefore need help understanding
it. Anyone approaching a new class should first try to understand its
behavior at the level of methods’ interfaces (i.e., their pre- and postconditions)
rather than at the level of
detailed
implementations. Programmers can then turn to detailed study of only those
methods they need to work with directly (e.g., debug). Approaching
the class in this fashion, students should appreciate how the modular design
of the class makes individual methods easier to understand.
The main method in BuggyRobot contains fairly comprehensive
tests of each of the other public methods: it tests each executing only its
base case, executing at least one recursion (for those methods that are recursive),
and in any other circumstance that might be unusual or interesting. As such,
we intended it to be a role model that students can emulate when they test
their own code. Instructors might want to explicitly point out such testing
desiderata as covering all the arms in an algorithm, or identifying and exercising
special cases in the problem that an algorithm solves, and how the tests in
BuggyRobot satisfy those desiderata (or fall short, if instructors
find gaps in our tests).
Instructors can vary this lab in a number of ways. In particular, they can plant different bugs, or remove some or all of ours. To create a shorter exercise, place bugs in only some of the public methods (ones without bugs can be removed completely, to make the class simpler, if desired); to make a longer exercise, add additional public methods with bugs. We deliberately placed all the bugs in the public methods, and placed only one bug in each method, to keep the lab simple. However, adding multiple bugs, or putting them in less obvious places, allows instructors to create more challenging versions of this lab.
We tried to plant “classic” bugs. For example, one involves not establishing proper preconditions prior to sending a recursive message, one involves not establishing postconditions in a recursive method’s base case, one involves not establishing the right postconditions in the recursive case etc. Instructors can replace these with other classic bugs, or with less classic ones, if they wish.
As mentioned above, we provided test drivers for all the buggy methods. The bugs we planted are also serious enough that they should manifest themselves in most or all tests. These features mean that testing is not a significant part of this exercise for students. This was a deliberate choice, allowing students to concentrate on the debugging process independently of test data selection, coding test drivers, etc. However, instructors who want to couple testing and debugging can do so by removing our test drivers and making students write their own.
All of these variations require that instructors create their own version of BuggyRobot.java. As a starting point for creating such customized versions, the Original can be found at http://www.charlesriver.com/algorithms/classes/BuggyRobot.java.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin