SUNY Geneseo, Department of Computer Science

Lab 8

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Wednesday, October 22

Purpose

Background

In this experiment you will work with two algorithms that find the largest value in an array of integers. Although both algorithms produce the same result, they do it in slightly different ways, which potentially impact the algorithms' execution times. The following sections describe the algorithms, and point you to readings on recurrence relations and experiments that may be helpful.

Finding the Largest Item in an Array

Suppose you want to find the largest item in an array of n integers. One approach is to first find the largest item in the first n-1 elements of the array and compare it to the last item in the array. If the last item is larger, return it, otherwise return the largest item in the first n-1 elements. You can think of the first n-1 elements of an n-element array as forming a slightly smaller array, in which case this approach yields a recursive algorithm that can be described as follows. Note that A is the array in which to find the largest item. Also note that for clarity in this pseudocode I assume that an n-item array has indices between 1 and n, although in Java such an array would have indices between 0 and n-1.

    findLargest( A, n )
        if n <= 1
            return A[n]
        else if A[n] > findLargest( A, n-1 )
            return A[n]
        else
            return findLargest( A, n-1 )

You might notice that in some cases this algorithm sends two recursive findLargest messages -- one to find the largest item in positions 0 through n-1 in order to compare it to A[n], and a second, if the comparison comes out false, to find the largest item in positions 0 through n-1 again, in order to return it. Being a little bit clever, you can find a more efficient algorithm (although still based on the same general idea). In particular, there is no need to send two recursive messages when you can send one and save the result in a local variable for later use:

    findLargest( A, n )
        if n <= 1
            return A[n]
        else
            previous = findLargest( A, n-1 )
            if A[n] > previous
                return A[n]
            else
                return previous

Your job in this lab is to determine mathematically how much more efficient the second algorithm is than the first, and then to experimentally test your analysis.

To help you get started on this lab, I have provided a Java class that represents arrays of integers that can find their largest element using the slow algorithm from above. You can find this class in file "SlowMaxArray.java" in our folder on the "Course Materials" server, or Download It from the Web at http://cs.geneseo.edu/~baldwin/csci141/fall2003/SlowMaxArray.java. There are a few differences between the Java and pseudocode versions of the algorithm that you should be aware of:

• The Java version is embedded in a complete class, the pseudocode presents just the maximum-finding algorithm
• The Java version gets the array from a member variable of the class, not as a parameter
• As already noted, Java array indices range from 0 to n-1, not 1 to n as assumed in the pseudocode. This will mainly affect the initial parameter value that main passes to findLargest.

You will need to define a similar class that uses the fast maximum-finding algorithm in order to complete the experimental program.

Different Classes that Handle the Same Message

In most object oriented programming languages, any number of classes can handle the same message. This is one aspect of an important feature of object oriented programming called polymorphism -- the ability to have messages handled differently depending on the kind of object to which they are sent. Java is no exception.

One of the things this feature allows is a way to change algorithms within a program with minimal changes to client code. To do this, simply define a new class that handles the message with the new algorithm, and replace the objects that originally handled the message with instances of the new class.

As an example of this technique, I want you to define your class that uses the fast maximum-finding algorithm so that it has as much as possible the same interface to clients as my class does. In particular, the message that makes instances of your class find their largest element should be named findLargest, and it should take the index of the last element to include in the search as its only parameter. Your class should also have a constructor that takes the desired array size as its only parameter. If you do this right, you should be able to change which algorithm your main program executes simply by changing the declaration and initialization of one object..

Recurrence Relations and Recursive Algorithms

Section 7.2 of The Science of Computing discusses recurrence relations, and how to use them to count the number of times a recursive algorithm does something. In this lab, the best thing to count is the number of findLargest messages that get sent when using each algorithm to search an array of n items. Remember to include in your count the message sent from the main program to start each search. You can set up recurrence relations that relate the number of each kind of message to n. The recurrence relations for both algorithms should be similar to ones discussed in Section 7.2.2 of The Science of Computing.

Experiments

See Chapter 4 of The Science of Computing for ideas about doing experiments in computer science. I am leaving much of the design of this lab's experiment up to you, but you should keep in mind guidelines for designing reliable experiments and collecting accurate data, avoiding what error you can and estimating the rest, etc. Note that you are likely to see outliers in this experiment's data.

Exercise

First, set up recurrence relations for the total number of findLargestmessages that get sent in order to find the largest item in an n-item array using each of the two algorithms presented above. For both algorithms, analyze the worst case numbers of messages. Find, and prove correct, closed forms for both recurrence relations. The recurrence relations and closed forms should give the number of messages as functions of n.

The closed forms you end up with are, theoretically, proportional to the actual running times of the algorithms. The second step in this lab is to design and conduct an experiment that tests this hypothesis. In other words, your experiment should test the hypothesis that the fast maximum-finding algorithm runs in time proportional to whatever function of n you derived from its recurrence relation, and that the slow algorithm runs in time proportional to the function you derived for it.

As Mentioned Above, I have provided a class, named SlowMaxArray, that implements the slow maximum-finding algorithm. You should define a class that implements the fast algorithm. Your class will need to have a name different from SlowMaxArray, but should otherwise have the same interface as SlowMaxArray. This will allow you to replace instances of SlowMaxArray with instances of your class in your main program with no changes other than to the declaration and initialization of the object in question.

When I tried this experiment, I encountered "stack overflow" errors that indicated I had run out of memory for the recursion when finding the largest element in arrays of more than about 4500 elements. You may well see this error too for large arrays -- it simply reflects the fact that computers have finite memories, and does not indicate that anything is wrong with your program.

Follow-Up