CSc 103 Lab

Empirical Algorithm Analysis


 
The purpose of this lab is to learn how to do timing studies to evaluate run time performance of algorithms.

Introduction

The big-O notations represent theoretical estimates for the running time of an algorithm. To be convinced in the correctness of these theoretical results, we want to do empirical analysis as well. Namely, we implement the algorithm (write a program for it), run it and see if the empirically observed running time behaves as predicted by theoretical analysis.

To be able to do empirical analysis, we need to run the program for different values of N (fairly large values) and see how the actual running time of the program changes depending on N's value. The expectation is the following: when N doubles, the running time goes up by factor of 2 for linear algorithms, by factor of 4 for quadratic algorithms, by factor of 8 for cubic algorithms. For a logarithmic algorithm the program will run only an additive constant longer when N doubles, and for O(NlogN) algorithms the time will be a little more than twice as long.

In this lab we will attempt to reproduce the results shown by the author in Figure 5.10 (pg 203).

The author provides the source code for his Max Subsequence Sum algorithms in MaxSumTest.java.

We are going to perform timing studies on his algorithms and create a table of results for running his programs on the CSL workstations.

Procedure

Replace the main method in MaxSumTest.java with one that performs the following tasks.

Prompt the user for the parameters for an execution:
Which algorithm (1-4) ?
How many items? (0 to quit)

Declare an array of size as specified by the user.
Fill the array with random integers between -50 and 50. (Suggestion: Use Math.Random() )
Display the time to fill the array.

Execute the method corresponding to the user's choice of algorithm.

Display the solving time in milliseconds.
Display the result (the max subsequence sum).
Repeat until user quits.



Note: To compute the actual time of a code segment, we need to get the current system time at the start of the segment (let's call it startTime), then get the current system time at the end of the segment (let's call it endTime). The running time of the segment will be the value of endTime - startTime. To obtain the current system time, we use
         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.


Experiment

Create a table in your favorite word processor with columns labeled as in Figure 5.10.

Run your program with all four algorithms for different input sizes, similar to Figure 5.10.   The lab computers are faster than the author's, so your results will be different.  You will likely need to use larger input sizes.

Run each algorithm three times for each size of input, and record the average.  (Start with algorithm 4, the fastest).


Conclusions

    1. Observe the difference of running times of different algorithms for the same value of N.

    2. Observe the growth rate of the running time of each algorithm for different values of N.  Perform the calculations based on your experimental data to determine the order of magnitude for the running time for each dataset. Show your calculations.

    3. Based on the calculations in step 2, determine whether your experimental observations are consistent with the theoretical predictions. If not, provide an explanation of the discrepancy.

     4.  Estimate how many times faster the lab computer is than the author's.

     5.  Export your document as a PDF and submit it to the PolyLearn assignment for lab 6. (Each student must submit a writeup.)

Optional.   Run the same experiment using the CSL server. (Open a terminal and enter ssh unix1.csc.calpoly.edu.) Create another table of results.  Which is faster, the lab computers or the CSL server?