CPE 103 Lab Activity
List Timing

Problem 6.12 from the textbook presents this problem:

The intersect method, shown below, returns the number of elements that are in
both lists. Assume both lists contain N items.
// Returns the number of elements in both c1 and c2
// Assumes no duplicates in either list.
public static int intersect ( List<Integer> c1, List<Integer> c2 )
{
    int count = 0;
    for( int i = 0; i < c1.size( ); i++ )
    {
        int item1 = c1.get( i );
        for( int j = 0; j < c2.size( ); j++ )
        {
            if( c2.get( j ) == item1 )
            {
                count++;
                break;
            }
        }
    }
    return count;
}
a. What is the running time of intersect when both lists are ArrayLists?
b. What is the running time of intersect when both lists are LinkedLists?



1. First, record your theoretical predictions to questions (a) and (b).

2. Plan a timing study to confirm your predictions experimentally.   You will need to run several trials with different sized datasets in order to determine relative running time.   Use increasingly large datasets until you observe a signficant difference, or can convince yourself that there isn't one.   Be sure to consider how to arrange the data so as to produce worst-case performance.

3.  Modify the method implementation so it uses a while loop instead of a for-loop with break, as described in the readings on structured programming.   Done correctly this should not effect the running time order of magnitude.

4. Write a JUnit test to verify the correctness of your method.

5. Instrument your code to determine the running time of the method. To obtain the current system time, use the
         long startTime = System.currentTimeMillis();
method of the System class located in java.lang library (no need to import). This method returns the current system time in milliseconds from midnight, 01/01/1970.

6. Run your experiment.  Create a neat table that records your observations with different sized lists.

7.  Perform the calculations based on your experimental data to determine the order of magnitude for the running time for each dataset. Show your calculations. Interpret the data, explaining whether or not it is consistent with your predictions. If your experimental results differ from your predictions, explain what you think might be the cause.

8.  Submit a printout of your written analysis and conclusions, the table of observations, and the source code from steps 3 and 4, (in that order).

Winter 2014 Instructions

8.  Submit your written analysis and conclusions, the table of observations, and the source code from steps 3 and 4, (in that order), as a PDF to the PolyLearn assignment for Lab 9.  Each student must write and submit their own report.