Laboratory Exercise

Lab 5 — Analysis of 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, and to use recurrence relations to derive operation counts for recursive algorithms. The exercise also provides practice designing recursive algorithms.

Prerequisites

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

Background

This exercise asks students to design, code, prove correct, and derive operation counts for 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

The “Colorful Line” 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.

Constructors in Subclasses

The “Colorful Line” algorithm should be coded as a method of a subclass of Robot. This subclass may 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 );

Strings

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.)

int length()
This message returns the number of characters in a string. For example, the following assigns the number of characters in string someString to variable count:
    int count = someString.length();
char charAt( int i )
This message extracts and returns the ith character of a string. Character positions are numbered from 0. For example, the following assigns the second character of someString to variable c:
    char c = someString.charAt( 1 );
String substring( int first, int end )
This message extracts and returns the portion of a string that starts with the character at position first in the string, and extends to but doesn’t include the character at position end. Character positions are numbered from 0. Thus, the following extracts the first 3 characters from string 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" + 2

For more information about the String class, see the Online Java API Documentation maintained by Sun Microsystems.

Exercise

For each of the following problems, design a recursive algorithm to solve the problem, code the algorithm in Java, prove that the algorithm is correct, and finally derive an expression for the number of operations the algorithm executes. Each exercise includes precise instructions concerning what kinds of operations to count, and what parameter to express the count in terms of.

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.

Colorful Line

Design, code, and prove correct a recursive algorithm that has one integer parameter, n, and that causes a robot to draw a line of length 2n + 1 in which the first (i.e., closest to the robot's initial position) n tiles are blue, the middle tile is yellow, and the last n tiles are red. You may assume as a precondition that there are no obstacles on the tiles the line will occupy.

When you are satisfied that your algorithm is correct, derive an expression for the total number of Robot messages it sends (i.e., move, turnLeft, turnRight, paint, okToMove, colorOfTile, and heading messages), in terms of n.

As an example of what the algorithm should produce, here is a colorful line with n = 2. The robot started where the bottom blue tile is, and ended (as shown) on the top red one:

[2 Red Tiles Above 1 Yellow Above 2 Blue]

Adopt (and state as comments in the algorithm) additional preconditions and postconditions regarding where the robot will stand, and how it will face, relative to the line. These will be helpful in designing the code around the recursive message(s).

Reversing a String

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”.

When you are satisfied that your algorithm is correct, derive an expression for the number of String operations (i.e., length, charAt, and substring messages, and string concatenation operations) that the algorithm executes, as a function of n (the length of the string).

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.

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 at the start of your lab session on Monday, October 18 (but it will be a very good idea to complete most of the work for this lab before the exam on October 7). Turn in printouts of the code you write, the correctness proofs and derivations of the operation counts, and the discussion of conclusions described below. The proofs, derivations, and conclusions can be in comments in the code, or on a separate piece of paper.

In addition to the code and analyses, write a brief (roughly one paragraph) discussion of the conclusions you can reach about the algorithms from the theoretical correctness and performance analyses. Here are some questions to think about, which might help you find some interesting conclusions to write about (you do not necessarily have to answer each, or even any, of these questions in your discussion — they are simply representative of the kinds of issues I want you to think about): Did you test your algorithms after coding them, or simply rely on the correctness proofs to tell you they would work? If you tested in addition to doing the proofs, why? In what, if any, ways did the correctness proofs or performance analyses help you design the algorithms? Do the results of the performance analyses let you compare the performance of the two algorithms? If so, in what ways? In what ways do the analyses not help you compare the algorithms’ performance?

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

Revised Sep. 29, 2004