Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
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.
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.
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.
The “Half Way Back from the Wall” problem uses 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.
The “Half Way Back from the Wall” algorithm should be coded as
a method 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 );The “Binary Numbers” problem involves generating the binary, or base two, representation of an integer. In binary form, a number is represented by a string of digits (just as in decimal, or base ten, form), but each digit must be either 0 or 1, and digit positions correspond to powers of two. The rightmost digit is the ones digit, the next digit is the twos digit, then the fours, the eights, and so forth.
For example, the binary number
1101
represents 1 one, 0 twos, 1 four, and 1 eight, i.e., 1 + 4 + 8, or the decimal number 13.
Similarly, the decimal number 9 is equivalent to 8 plus 1, or the binary number
1001
(1 eight, 0 fours, 0 twos, and 1 one).
The “Reversing a String” exercise requires manipulating strings.
Strings in Java are objects, instances of the standard library class String.
Some messages to strings that are likely to be particularly useful in
this exercise are described below.
(The descriptions use a convention
that is widely used in user documentation of messages: each message is introduced
by showing how it could be declared inside the class that implements it. Note
that this is not what a programmer writes in order to use
the message, rather it is a compact way to provide complete information on
the message’s
name, the number
and types of parameters, the type of result, etc. For example, the message
description “char charAt( int i )” says that there is a message
named “charAt”,
which has one parameter, that parameter is an integer, and the message returns
a character. A programmer can thus deduce that uses of this message
could look like c = obj.charAt(7), or System.out.println(
obj.charAt(i) ), and so forth, where c is
a char variable, i is an integer variable,
and obj is whatever sort of object handles the charAt message
— a String in this particular case.)
someString to variable count: int count = someString.length();someString to variable c: char c = someString.charAt( 1 );someString: String firstThree = someString.substring(0,3);Finally, programmers can concatenate strings and other values into longer strings using the “+” operator. When applied to a string and just about any other kind of value, “+” converts the other value into a string if necessary, and concatenates that string with the “+’s” other operand. For example, the following constructs the string “aardvark” by concatenating two shorter strings:
"aard" + "vark"The following creates the string “Sally2” by converting the integer 2 to a string and concatenating it to the string “Sally”:
"Sally" + 2For more information about the String class, see the Online
Java API Documentation maintained by Sun Microsystems.
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.
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
Code this algorithm as a method of a subclass of the Robot class.
See the information on Robots and Constructors
in Subclasses in the “Background” section
for information on using the robot and writing subclasses of it.
Design, code, and prove correct a recursive algorithm that takes a non-negative integer as its parameter, and that returns a string containing the binary representation of that integer. A review of Binary Numbers appears in the “Background” section of this document.
Code this algorithm as a static method of the main class.
Design, code, and prove correct a recursive algorithm that takes a string as its parameter, and that returns the reversal of the string (i.e., the string written backwards). More formally, the algorithm’s main postcondition is that if the input is an n-character string, c1c2…cn-1cn, then the output is the string cncn-1…c2c1. For example, reversing “abcd” yields “dcba”.
Information on Java Strings and some messages to them that are likely to be useful in this exercise appears in the “Background” section of this document.
Code this algorithm as a static method of the main 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.
Turn in your solution to this exercise as directed by your instructor.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 8, 2005 by Doug Baldwin