University of North Carolina at Asheville

CSCI 202: Introduction to Data Structures


Lab 11: Performance of Algorithms

[Introduction] [Instructions] [What To Submit]


Introduction

In this lab you will implement and test the time performance of several algorithms that must process large arrays of integer values in some fashion. You will make your tests using a Java GUI application that plots the performance time of an algorithm as a function of the number N of values to be processed.

The GUI test application has already been written for you. Its initial window appears as shown below:

The top panel contains several text boxes. The leftmost box is labeled Testable. You must use this box to specify the class containing the method to be tested. This method must do something to an array of N integers. Its time performance will be measured for a sequence of input arrays, all of different sizes. The initial array size is the minimum, and is specified in the textbox labeled Min N. As you can guess, the final (maximum) size is entered in the textbox labeled Max N. The method will be tested over a range of sizes between these values, stepping up from the initial minimum size in fixed increments. And of course the size increment is specified in the textbox labeled Increment.

The role of the rightmost textbox, labeled Repetitions, is perhaps not so obvious as the others. It is there because computers are so fast that most of the tests we will be making here will run to completion in very short times, typically much less than one millisecond (ms). The GUI framework makes its time estimates via operating systems calls to get the start and end times, which are in milliseconds. Since a single execution of a method takes so little time, we must repeat the same method call many times and take the average of the total time to get a reasonable measurement of the time per repetition.

The initial display shows defaults for all these values. If you press the Start button in the bottom control panel, you will launch a test of a sample method that implements the notorious bubble sort algorithm that was discussed in class. The final test results should appear as shown below:

In this lab you will implement and test a few methods of your own using this test framework.


Instructions:

To complete this project, follow the steps listed below:

  1. Download the JAR file
    Lab11Project.jar

    directly into your csci/202/labs folder. Then launch a terminal window to extract your complete starting project folder from this JAR file.

  2. Launch the NetBeans IDE, select the File/Open Project... option in the toplevel menu bar, and open the Lab11 project you extracted in the previous step.
  3. Now find the package named mytests in your Lab11 project. This package initially contains only one class, named Adder. Open the source code for this class, and note that it implements an interface named framework.Testable. This interface requires only one method, which has the header
    
    public void process (Integer [] values, int nvalues); 
    
    As you can see, this class has exactly one (stubbed) method with that header. Your first task is to insert code into that method which finds the sum of the first nvalues components of the input array values. For the purposes of this test, the method should simply exit as soon as it finds the sum, without even bothering to print it.

    Once you have implemented this method, use the GUI framework to study its time performance. You will probably have to play with the topmost text boxes to get meaningful results...

  4. When you have reached this point, your lab instructor will have a few more algorithms for you to implement and test in a similar fashion. Each one should be implemented as a new class implementing the Testable interface, and each should be added to the mytests package.
  5. Once you have completed the implementation of all these algorithms, demonstrate their time performance to your lab instructor.


What To Submit

Before you exit NetBeans, clean your expanded Lab11 project. Finally, before you logout, open a terminal window and use the cd command to enter your csci/202/labs directory. Then re-create a JAR file of your Lab12 project folder, using the command

jar cf Lab11Project.jar Lab11
Please leave both the project folder and Lab11Project.jar in your csci/202/labs directory for the remainder of the semester.