SUNY Geneseo, Department of Computer Science

Lab 5

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Wednesday, October 1

Purpose

This lab's goal is to further develop your ability to design and think about recursive algorithms, including your ability to use induction to reason about their correctness. The lab does these things by asking you to design and prove correct a couple of recursive algorithms.

Background

You can find examples of induction proofs about recursive algorithms in Section 7.1.2 of The Science of Computing.

In this lab you will be using the Robot class you have used in other labs. Documentation for this class is on the Web, at http://cs.geneseo.edu/~baldwin/sc/doc/. You can find code for the Robot and RobotRoom classes on the Web at http://cs.geneseo.edu/~baldwin/sc/Robot.java, and http://cs.geneseo.edu/~baldwin/sc/RobotRoom.java, or in our folder on the "Course Materials" file server.

Exercise

Design and code a subclass of Robot that has the following methods. Each method you write for the subclass should be recursive. In addition to coding the methods in Java and testing them, give a mathematical proof that each is correct.

colorfulLine

A method that has one integer parameter, n, and that draws a line of length 2n + 1 such that the first (i.e., closest to the robot's initial position) n tiles in the line are blue, the middle tile is yellow, and the last n tiles are red. For example, here is the result of a colorfulLine( 2 ) message. The robot started at the bottom of the line, and ended (as shown) at the top:

[2 Blue Tiles, 1 Yellow, and 2 Red]

pyramid

A pyramid is a roughly triangular pattern of painted tiles, such as the following:

[Diagonal Lines Meeting at a Common Tile]

The height of a pyramid is the number of rows of tiles in it. For example, the above pyramid has height 3.

Give your subclass a pyramid( n ) method that makes a robot draw a pyramid of height n. You may assume that no walls will interfere with the robot drawing the pyramid. The main postcondition is that a height n pyramid is painted in the robot's room.

This method will be considerably easier to write correctly if you adopt additional preconditions and postconditions to say where the robot should be standing, and what direction it should be facing, relative to the pyramid.

halfwayBack

A method 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 gives you 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 (rounded down if n is odd) tiles between the robot and the wall
  2. Those tiles are yellow
  3. The tiles between the robot's final position and its starting position (not counting the starting tile itself) are green
  4. The robot is facing away from the wall.

This is the trickiest method in this lab. It really will be easiest to get right if you prove pieces of its correctness to yourself as you write it -- i.e., use an informal correctness proof to convince yourself that you are writing the right things as you write them. You will probably use recursion in a slightly more complicated way than you did in past labs, and you will correspondingly use induction in a slightly different way than you did for the earlier algorithms in this lab.

Follow-Up

Turn in printouts of the code you wrote, and the correctness proofs, by the end of the due date. The proofs can simply appear in comments in the program, or they can be on a separate sheet of paper, whichever you prefer.