CSc 150

Part 1: Source Code and Algorithm Analysis

1. public void one(int n)
   {   
      int a;   
      for (int i=n; i>0; i-=2)
         a=i;
   }
   

2. public void two(int n, int p)
   {
      int a;
      if (p>0)
      {
        for (int i=0; i<n; i++)
          for (int j=1; j<=n; j++)
             a=i*j;
      }
      else
      {
        for (int i=0; i<n; i++)
          a=i;
      }
   }
   

3. public void three(int[] myArray)
   {
      int n=myArray.length;
      int count=0;
      do
      {
         count++;
         n=n/2;
      } while (n>1);
      n=myArray.length;
      for (int i=1; i<=count; i++)
        for (int j=0; j<n; j++)
          System.out.print(i*myArray[j]);
   }
   

   Unfamiliar with Java's do-while loop? Check out this tutorial or any number of others just by Googling it.

4. public void four(int n, int p)
   {
      int a;
      for (int k=0; k<p; k++)
      {
         System.out.println(k);
      }
      for (int i=1; i<=6; i++)
         this.one(n);   // call to method "one" above
   }
   

5. public void five(int[] A, int[] B)
   {
      int n=A.length;
      int m=B.length;
      for (int i=0; i<m; i++) {
        for (int j=0; j<=i; j++) {
          B[i]=j;
        }
      }
      for (int p=n-1; p>=0; p--) {
        for (int q=p-1; q>=0; q--) {
          A[p]=q;
        }
      }
   }
   

Part 2: Run-time Analysis

Go to our BlackBoard web page and download two files from the Course Material section. The first is the compiled code for six different sorting methods, called Sort.jar. It has the following public interface:

public class Sort
{
   public static int[] method1(int[] A)
   {
      // returns a new sorted array. The array A is not changed.
   }

   public static int[] method2(int[] A)
   {
      // returns a new sorted array. The array A is not changed.
   }

   public static int[] method3(int[] A)
   {
      // returns a new sorted array. The array A is not changed.
   }

   public static int[] method4(int[] A)
   {
      // returns a new sorted array. The array A is not changed.
   }

   public static int[] method5(int[] A)
   {
      // returns a new sorted array. The array A is not changed.
   }

   public static int[] method6(int[] A)
   {
      // returns a new sorted array. The array A is not changed.
   }

   // getMethod<X>Count: returns the number of array accesses
   // that occurred in the last execution of the method.

   public static long getMethod1Count()
   public static long getMethod2Count()
   public static long getMethod3Count()
   public static long getMethod4Count()
   public static long getMethod5Count()
   public static long getMethod6Count()
} // end of class Sort

The second file you need to download is Client.java. This is the source code containing the main() method that runs each of the above sorting methods.

Setup

Once your project is runnable, be sure to study the Client.java file to understand what's going on. Notice that there are two ways in which the time complexity of the sorting methods is being measured:

1. The code is measuring the time in milliseconds of execution of each method (using the currentTimeMillis() method of System)
2. The code is counting the number of array accesses the method makes.

Your Mission

Using this data, I want you to make two plots for each method:

1. A plot of the time each of the array content types (random, sorted, etc.) takes (on the vertical axis) against the array length (on the horizontal axis)
2. A plot of the number of array accesses each of the array content types makes (on the vertical axis) against the array length (on the horizontal axis)

Notes:

• Please turn in paper copies of your graphs, but I also want to see the actual raw data that you obtained (in an organized way). If you don't wish to waste paper, you can turn in your graphs as an Excel file on BlackBoard.

• The thoroughness of your tests play a big role here. You should alter the main() method in many ways to make sure you get the worst-case complexity. How does the method fare on random lists of numbers? On a list that's already sorted? On a list that's sorted in reverse? On a list of identical numbers? And, of course, you must be vigilant about trying all kinds of array sizes. Don't be discouraged if you start getting strange or even negative numbers. A negative number usually means the variable overflowed its capacity (you tried to store a number that was too big for it to handle). Just use data that you got up to that point. And if you start waiting too long for it to finish (more than 10 minutes), don't use a bigger array than that. You could, however, comment out the other methods and test each one individually! Try to test as big an array as you reasonably can. You'll need at least 10 data points for each type and length of array that you test in order to be reasonably sure that you can see the pattern.

• Use more than just the graphs for determining the time complexity. Remember that virtually all complexities greater than O(n) look like concave-up curves. So use the numeric data too. If you think something is O(n²), then if you double the data size, you ought to quadruple the number of steps.

• You should treat this project like a physics or chemistry experiment in which you are making measurements and making conjectures based on your measurements. Therefore a significant number of points will be taken off if you have not sufficiently tested the algorithms or if you have not sufficiently analyzed your results. Make sure your plots are clear, well-labeled, neat, etc. You need to include a discussion of the tests you made so that I can understand where your data came from. The harder it is for me to understand what you did, the fewer points you will receive.

Gentle Reminder