Analysis of Algorithms
Lab

Advanced Programming/Practicum
15-200

Introduction In this lab you will run driver programs for two tasks: (1) sorting (driver) (2) finding the minimum distance between two points in the plane (driver). While running these drivers (as instructed below). you will record their measurements to fill in a spreadsheet. Please download these three zip files now. Start Eclipse and (unzip and) load the first two (as projects); double click the spreadsheet to start Excel. Note: if you are on a PC, you can run the batch files in the executable subdirectories.

Sorting To run the sorting driver,
  • Initially, select a size of 1,000.
  • Choose random values (the default).
  • Choose NOT to print before/after values (the default).
  • Choose NOT to verify that the array is sorted (NOT the default).
  • Choose an O(N^2) sorting method (b, s, or i).
    Write in the method in B1 of the spreadsheet.
  • Choose to sort this same array 10 times.
  • Write in the Fastest, Slowest, and Average times in the appropriate column of the spreadsheet; other cells will automatically be filled in.

  • Choose a new array (n) and repeat the above process for sizes 2,000, 4,000, 8,000, and 16,000 element arrays.
Repeat this process for an O(N log N) sorting method (m, q, h, or a) for arrays containing 50,000, 100,000, 200,000, and 400,000, and 800,000 elements

  1. Notice how doubling in size affects the average running time of each method (the Ratio rows).

  2. Notice the Spread when sorting the same arrays; this gives a bound on the accuracy of any such computations.
  3. Generally, Java's system clock is accurate only to about 1 millisecond (.001 seconds).

  4. Notice the simple computation of C for the equation T(N) = ... (look at the cell; this would be easy to do on a calculator and easy to do by hand if you can estimate the logarithmic function).

  5. Notice the Error when using just the last N and T(N) to compute C and using it to predict the other times.

Minimum Distance To run the minimum distance driver,
  • Initially, select the brute algorithm.
  • Select # of Points to be 1,000.
  • Select # of test arrays to be 5 (the default).
  • Select # of times to test each array to be 5 (the default).
  • Choose to NOT Display points (the default).
  • Choose NOT to calculate via brute force (for checking) (SOMETIMES the default).
  • Write in the average times in the appropriate column of the spreadsheet; other cells will automatically be filled in.

  • Choose to test again (the default) using the same information but larger # of points: 2,000, 4,000, 8,000, and 16,000.
Repeat this process for the other methods (sort and hash) for 50,000, 100,000, 200,000, and 400,000, and 800,000 points.

  1. Notice how doubling in size affects the average running time of each method (the Ratio rows).

  2. Notice the simple computation of C for the equation T(N) = ... (look at the cell; this would be easy to do on a calculator and easy to do by hand if you can estimate the logarithmic function).

  3. Notice the Error when using just the last N and T(N) to compute C and using it to predict the other times.

  4. Notice that C for sort is 40 times as large as C for hash. As N gets bigger, the time for hash is growing more slowly than the time for sort. Given these numbers, about big does N have to be for hash to be faster than sort? Hint: Solve the equation Ch * N = Cs * N log N for N, with Ch representing the C for hashing and Cs representing the C for sorting.