SUNY Geneseo, Department of Computer Science

Solutions for Exam 1

CSci 141 , Fall 2004

Prof. Doug Baldwin

These are my solutions to the questions from Exam 1. Some of my comments on graded exams refer you to these solutions. Any questions you have about these solutions or other aspects of the exam are, of course, welcome at any time and in any form.

Question 1

(Write a recursive algorithm that turns a robot to a specified heading, and then back again to its original heading.)

The recursive insight is that if the robot turns one step to its left (if it isn't already facing in the desired direction), it then has a smaller distance to turn and come back from. It can solve this smaller problem recursively. Upon finishing the smaller problem, the robot has to turn one step to its right, to undo the first left turn:

    // In some sublcass of Robot
    void turnAndReturn( int desiredHeading ) {
        if ( this.heading() != desiredHeading ) {
            this.turnLeft()
            this.turnAndReturn( desiredHeading )
            this.turnRight()
        }
    }

Question 2

(Describe the following code, using the words "subclass," "inherit," "message," and "method."

    class SuperRobot extends Robot {

        public void turnAround() {
            this.turnLeft();
            this.turnLeft();
        }

        public void paintAndMove( java.awt.Color c ) {
            this.paint( c );
            this.move();
        }
    }

)

This code defines a "SuperRobot" subclass of the Robot class. As a subclass, SuperRobot inherits all the features of Robot, e.g., methods for moving, turning, etc. Instances of the SuperRobot class handle two messages that Robot does not, however, namely "turnAround" and "paintAndMove."

Question 3

(Consider the following algorithm for adding up the values in positions 0 through i of a SuperArray:

    // In class SuperArray...
    int addValues( int i ) {
        if ( i == 0 ) {
            return A[0]
        }
        else {
            return this.addValues( i-1 ) + A[i]
        }
    }

Part A asks you to prove this algorithm correct; part B asks you to derive the number of references to elements of A that it makes as a function of i.)

Part A

The proof is by induction on i.

For the base case, consider i = 0. In this case, the "if ( i == 0 )" test succeeds, and the algorithm returns A[0]. This is the sum of all the values between positions 0 and 0.

For the induction hypothesis, assume that for some k-1 >= 0, addValues(k-1) returns the sum of the values in positions 0 through k-1 of the SuperArray.

Show that addValues(k) returns the sum of the values in positions 0 through k: Since k-1 >= 0, k > 0 and so the "if ( i == 0 )" test fails. The algorithm therefore returns addValues(k-1) + A[k]. By the induction hypothesis, the first term in this sum is the sum of the values in positions 0 through k-1 of the SuperArray. Adding A[k] to this sum yields the sum of the values in positions 0 through k, as was desired.

Part B

Set up a recurrence relation for R(i), the number of references to A as a function of i. When i = 0, the algorithm makes one reference in order to return A[0]. When i > 0, the algorithm makes one reference to A[i], plus however many the recursive message makes. The recurrence relation is thus

• R(i) = 1 if i = 0
• R(i) = 1 + R(i-1) if i > 0

Looking at values of R(i) for a few small values of i suggests that R(i) = i + 1:

Prove that R(i) really does equal i + 1 by induction on i:

Base case, i = 0: R(0) = 1, from the recurrence. 1 = 0 + 1.

For the induction hypothesis, assume that R(k-1) = (k-1) + 1 = k, for some k-1 >= 0.

Show R(k) = k + 1: R(k) = 1 + R(k-1) from the second line of the recurrence and the fact that if k-1 >= 0 then k > 0. 1 + R(k-1) = 1 + k, from the induction hypothesis.

Question 4

(Analyze a set of times for a robot to handle various numbers of "move" messages, to determine if the times are consistent with the hypothesis that a "move" message takes 500 milliseconds to handle.)

Data analysis consists of finding an average time for each number of moves, and then calculating a time per move from these averages. Extending the original table with these calculations yields...

The times per move are all within about 0.3 percent of the hypothesized 500 mS, so I would say the data support the hypothesis.