Laboratory Exercise

Lab 5 — Induction and Recursive Algorithms

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004

Purpose

This exercise develops students’ abilities to think inductively about recursion, in particular to use induction to prove recursive algorithms correct. The exercise also provides practice designing recursive algorithms.

Prerequisites

Understanding of Chapter 6 of Algorithms and Data Structures: The Science of Computing.

Understanding of Section 7.1 of Algorithms and Data Structures: The Science of Computing.

Background

This exercise asks students to design, code, and prove correct several recursive algorithms. Correct algorithms for the problems in this lab aren’t necessarily obvious. Thinking inductively about the algorithms (i.e., assuming that recursive messages will establish their postconditions for smaller instances of a problem, analogous to assuming that smaller instances of a proposition are true in an induction hypothesis) will make them easier to design, and rigorous proofs of their correctness may well uncover flaws in the original designs.

Robots

Several problems in this lab use the robot introduced in Chapter 2 of Algorithms and Data Structures: The Science of Computing. This robot is available as 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.

Constructors in Subclasses

Several of the algorithms in this lab should be coded as methods of a subclass of Robot. This subclass will need constructors. A constructor is basically a method that initializes a new object (see Sections 3.4.2 and A.4.4 of Algorithms and Data Structures: The Science of Computing). In Java, constructors have the same name as the class they initialize — for example, the constructors for Robot objects are named Robot, the constructors for instances of a hypothetical ExtendedRobot subclass of Robot would be named ExtendedRobot, and so forth. Note that subclasses don’t inherit constructors from their superclass the way they inherit other methods — for example, even if a constructor for Robot logically does everything necessary to initialize instances of an ExtendedRobot subclass, there is no way to automatically apply this constructor to ExtendedRobot objects.

Even though Java doesn’t do it automatically, one often wants to initialize instances of a subclass by just calling a superclass’s constructor. This will probably be the case for the subclass of Robot defined in this lab. To do this, define constructors for the subclass that do nothing but call the corresponding superclass constructor. Within a constructor, the word super can be used to call a superclass constructor. For example, to allow instances of an ExtendedRobot subclass of Robot to be initialized with their position, heading, and room (just like the four-parameter constructor for Robot does), include the following constructor in ExtendedRobot:

    // Within the ExtendedRobot class...
    public ExtendedRobot( int column, int row, int heading, RobotRoom room ) {
        super( column, row, heading, room );
    }

A statement such as the following implicitly uses this constructor to initialize an extended robot:

    ExtendedRobot r = new ExtendedRobot( 1, 3, Robot.NORTH, myRoom );

Exercise

For each of the following problems, design a recursive algorithm to solve the problem, code the algorithm in Java, and prove that the algorithm is correct.

Think about the proof while designing each algorithm, not afterwards. For example, while designing an algorithm’s base case, think about why that code correctly solves the smallest instance of the problem; while designing the recursive case, think about why, if recursive messages correctly solve smaller problems, the recursive case correctly solves a larger problem. Such concurrent design and proof greatly increases the chances of designing a correct algorithm on the first try, and generally makes the algorithms easier to develop.

Multiplication

Design, code, and prove correct a recursive algorithm that takes two integer parameters, a and b, and that returns their product, ab. The algorithm must compute this product using only addition, subtraction, and comparison operations. You may assume as preconditions that a >= 0 and b >= 0. (Hint: consider that 0b = 0 no matter what b is, and that ab = (a-1)b + bfor any a > 0.) You may code this algorithm as a static method of your program’s main class.

Bouncing

Design, code, and prove correct a recursive algorithm that moves a robot forward until it comes to a wall (or other obstacle), and then makes the robot “bounce” back to a tile three times as far from the wall as the tile the robot started on. More precisely, the relevant postcondition is that if the robot started with n tiles (not counting the tile the robot was on) in front of it between it and the wall, then the robot ends with 3n tiles behind it between it and the wall. Assume as a precondition that when the robot starts with n tiles between it and a wall, facing that wall, there are no obstacles on the 2n tiles behind the robot.

Half Way Back from the Wall

Design, code, and prove correct a recursive algorithm that makes a robot move forward until it comes to a wall, and then come half way back to where it started. As the robot moves towards the wall, it should paint the tiles it comes to green; as it comes back, it should paint tiles yellow (this provides a way to see at the end where the robot started, and whether it moved back the right distance).

To say precisely what this method should do, suppose the robot starts with n tiles between it and the wall (not counting the tile the robot is on, i.e., n = 0 if the robot is next to a wall). Then the method’s postconditions are

  1. There are ⌊n/2⌋ tiles between the robot and the wall, not counting the tile the robot is on (Note: ⌊…⌋ denotes rounding non-integers down to the next lower integer, and does not affect integers).
  2. Those tiles are yellow
  3. The tiles between the robot’s final position and its starting position (counting the tile the robot ends on, but not counting the starting tile itself) are green
  4. The robot is facing away from the wall.

Final Details

The Robot Class

Students can download both Robot.java and RobotRoom.java 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

This lab is due on Monday, February 21. Turn in a printout of the your code, showing the algorithms you designed for each exercise as well as the main method. Also turn in your correctness proof for each algorithm. These proofs can be comments in your code, or on a separate piece of paper.

Finally, turn in a sentence or two commenting on any interactions that you noticed between correctness proofs and algorithm design in this lab. For instance, you might comment on whether constructing proofs helped you understand the algorithms you were designing (and if so, how), whether the ideas around which you designed your algorithms helped you write the proofs (and if so, how), whether the proofs you did actually helped you find any bugs in your algorithms, etc. These sentences can appear as comments in your code, or on a separate sheet of paper.

Portions copyright © 2004. Charles River Media. All rights reserved.

Revised Feb. 14, 2005