SUNY Geneseo, Department of Computer Science

Lab 6

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Wednesday, October 8

Purpose

This lab is designed to introduce you to recurrence relations, by demonstrating the connections between theoretical results about recursive algorithms derived via recurrences and the observable behavior of those algorithms.

Background

The Science of Computing presents an analysis of the following algorithm to move a robot forward a given distance (see Section 7.2.2, page 291):

    public void takeJourney (int distance) {
        if (distance > 0) {
            move();
            takeJourney (distance - 1);
        }
    }

By setting up a recurrence relation based on the recursion in the algorithm, the book concludes that this algorithm uses n move messages to move the robot a distance of n tiles.

Your job in this lab is to carry out an experiment that tests the results of this analysis.

Exercise

Design and conduct an experiment that tests a two-part hypothesis based on the analysis described in the "Background" section:

  1. The takeJourney algorithm sends n move messages in order to move a robot a distance of n tiles
  2. The time that takeJourney requires to move a robot n tiles is proportional to n.

Your experimental program will need a robot that can carry out the takeJourney algorithm, while counting how many move messages get sent. I will talk in lab about a way to use subclasses and method "overriding" to do this.

To test the second hypothesis, you will need to analyze the times you collect to see if they are proportional to n. Thinking about what "proportional" means may help you see a way to do this analysis. If not, ask and I will give you suggestions.

Most of the other things you need for this experiment are ones you already have experience with -- timing code, setting up reliable experiments and collecting data, etc. If you have questions, feel free to ask, or consult Chapter 4 of The Science of Computing.

Follow-Up

Turn in a report describing your experiment and the conclusions you reached from it. As for the last experiment you did, I expect a couple of pages (plus a printout of the experimental program) to suffice for this report.