Instructor Notes

Object Oriented Programming Lab

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 pertain to the laboratory exercise entitled “Object Oriented Programming in Java”. The notes explain our goals in designing the lab, and offer tips for helping students do the exercise.

The Lab’s Design

The first of these goals helps students understand the key object oriented abstractions introduced in Chapter 2 of Algorithms and Data Structures: The Science of Computing. The second goal allows students who have forgotten basic Java features (or who learned to program in a different language) a chance to regain the level of Java proficiency we assumed readers of Algorithms and Data Structures: The Science of Computing would have.

Working with Subclasses and Objects

We want this lab to give students practice defining a subclass in Java. However, we expect this lab to be students’ first hands-on work with subclasses, so the subclass is simple. We also want to give students a chance to create objects and send messages to them. Connecting this with the subclass students define, we want students to personally see that instances of the subclass handle messages whose methods are inherited as well as messages whose methods the students defined in the subclass. Part 1 of the lab provides the practice defining a subclass; Part 2 provides the practice using instances of it.

The subclass students write illustrates subclasses as a way of extending the functionality of their superclasses (i.e., the definition of “subclass” that Algorithms and Data Structures: The Science of Computing emphasizes). Keeping this illustration of subclasses simple, defining it requires little more than that students know the basic syntax for defining a subclass, use the special variable this, and write constructors that call analogous constructors in the superclass. In particular, we deliberately do not ask students to deal with advanced elements such as overriding inherited features, abstract methods, etc.

The most sophisticated element of object oriented programming in this lab is the travel message. This message has two overloaded forms: a parameterless one that makes a robot move until it comes to an obstacle, and a one-parameter one whose parameter is the number of tiles the robot should move. These are the two most logical ways of moving multiple tiles (i.e., “travelling”) in the robot environment. Overloading a single message name with both functions is thus a reasonably natural thing to do, and provides an opportunity to introduce students to overloading (something they will see frequently in object oriented programming anyhow). Instructors may simplify the exercise slightly, however, by renaming one message to avoid exposing students to overloading.

In Part 2, we deliberately ask students to create two instances of their subclass. Novices often have trouble understanding the difference between classes and objects, and explicitly creating multiple instances of a single class helps clarify the difference. This is particularly true when the objects are visible as distinct entities on the student’s monitor.

Basic Java

We selected the specific messages handled by the subclass in part to encourage students to use a variety of control structures:

Object Oriented Problem Solving

While not a primary goal of this lab, Part 2 offers students a fairly challenging exercise in algorithmic problem solving. There is no immediately obvious way to move two robots so they are standing next to each other, since robots cannot “see” tiles other than the one immediately in front of them, and can only tell whether that tile is occupied or not, not whether the occupant is a robot as opposed to a piece of wall. While this problem may be one of the hardest parts of the lab for many students, we feel that it is a good application of the subclass from Part 1, a good exercise in object oriented programming, and the practice in problem solving is a desirable side benefit.

There are many ways to solve this problem. All will be easiest if students approach them top-down, and take the time to design their algorithm before they start to code it.

As we hint in the lab assignment proper, some of the messages defined for the subclass will be helpful in solving this problem. We specifically imagine a number of solutions using the parameterless travel message, and face. If students identify other “building blocks” that help them solve the problem, they can be encouraged to abstract those building blocks into additional messages for their subclass.

We also use this problem as an opportunity to give students experience interpreting pre- and postconditions as formal specifications of a problem.

Tips

Many students will have trouble solving the problem in Part 2. A good basic strategy is to move both robots as close as possible to some recognizable point, for instance a corner of the robots’ room. The main complicating factor is that either robot may block the natural path for the other to that point. Some students may not realize that this complication exists at all; others will realize that it exists, but will not devise code that correctly handles all possible conflicts. Showing students code to solve a similar problem (e.g., navigate a robot around an obstacle whose exact position is unknown) in advance of the lab will help many students (so much so, in fact, that some instructors may view such an example as spoiling the exercise). For students who need more detailed guidance, try explicitly suggesting top-down design, planning before coding, and identifying abstract steps that correspond to subclass messages.

Many students also have trouble finding basic Java control structures for the tasks that the subclass’s methods need to do. Often, asking leading questions (e.g., “can you think of a control structure that might help here”, “what sort of loop have you used in the past when you know in advance how many times to repeat”) provides all the guidance these students need.

Some students misunderstand the meaning of “precondition”, specifically, thinking that a precondition is something that an algorithm needs to verify before it does its central task. Because this lab explicitly uses preconditions in the specifications for subclass methods, doing the lab will expose such misconceptions, and give instructors a chance to correct them, either in conversation with students during the lab, or while grading it.

Some students will inevitably have problems using Java syntax correctly during this lab. Indeed, part of the lab’s point is to make students face such problems and begin to overcome them. Reminding students about the appendix to Algorithms and Data Structures: The Science of Computing, and encouraging them to use it as a tool for individual study, can help students overcome immediate problems in this lab, and improve their ability to solve similar problems independently in the future.