This is the interface

public interface SER222_02_01_HW02_Submission { /* * Generates an array of integers where half the data is 0s, half 1s. * @param size number of elements in the array. * @return generated test set. */ public Integer[] generateTestDataBinary(int size); /** * Generates an array of integers where half the data is 0s, half the * remainder is 1s, half the reminder is 2s, half the reminder is 3s, and so * forth. * * @param size number of elements in the array. * @return generated test set. */ public Integer[] generateTestDataHalfs(int size); /** * Generates an array of integers where half the data is 0s, and half random * int values. * @param size * @return */ public Integer[] generateTestDataHalfRandom(int size); /** * Computes the double formula value for two run times. * * @param t1 first time * @param t2 second time * @return b value */ public double computeDoublingFormula(double t1, double t2); /** * Computes an empirical b value for insertion sort by running it on a pair * of inputs and using the doubling formula. * * @param small small test data array * @param large large test data array. twice the same of small array. * @return b value */ public double benchmarkInsertionSort(Integer[] small, Integer[] large); /** * Computes an empirical b value for shellsort sort by running it on a pair * of inputs and using the doubling formula. * @param small small test data array * @param large large test data array. twice the same of small array. * * @return b value */ public double benchmarkShellsort(Integer[] small, Integer[] large); /** * Runs the two sorting algorithms on the three types of test data to * produce six different b values. B values are displayed to the user. * * @param size size of benchmark array. to be doubled later. */ public void runBenchmarks(int size); }

---------------------------------------------------------------------------------------------------

This is where you implement the interface

public class BaseNonUniform implements SER222_02_01_HW02_Submission { /*************************************************************************** * START - SORTING UTILITIES, DO NOT MODIFY (FROM SEDGEWICK) * **************************************************************************/ public static void insertionSort(Comparable[] a) { int N = a.length; for (int i = 1; i 0 && less(a[j], a[j-1]); j--) exch(a, j, j-1); } } public static void shellsort(Comparable[] a) { int N = a.length; int h = 1; while (h = 1) { // h-sort the array. for (int i = h; i = h && less(a[j], a[j-h]); j -= h) exch(a, j, j-h); } h = h/3; } } private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)

//TODO: implement interface methods.

public static void main(String args[]) { SER222_02_01_HW02_Submission me = new BaseNonUniform(); int size = 4096; //NOTE: feel free to change size here. all other code must go in the // methods. me.runBenchmarks(size); } }

-------------------------------------------------------------

public class Stopwatch {

private final long start;

/** * Initializes a new stopwatch. */ public Stopwatch() { start = System.currentTimeMillis(); }

/** * Returns the elapsed CPU time (in seconds) since the stopwatch was created. * * @return elapsed CPU time (in seconds) since the stopwatch was created */ public double elapsedTime() { long now = System.currentTimeMillis(); return (now - start) / 1000.0; } }

2 Requirements (36 points] For this assignment you will be writing code to generate test data and benchmark sorting algorithms on it (edited from Sed gewick and Wayne: 2.1.36). Already provided for you is BaseNon Uniform.java which con- tains the existing sorting algorithms. This class extends an interface called SER 222_02_01_HW02_Submission which defines all of the methods that you need to create. You may create additional private helper methods. First, write a series of methods to generate test data that is "non-uniform": Implement the method public Integerd generate Test Data Binary(int size). Half the data is Os, half 1s. For example, an input of length 8 might look like [0, 0, 0, 0, 1, 1, 1, 1). See the interface. [4 points] Implement the method public Integerll generate Test Data Halfs(int size). Half the data is 0s, half the remainder is ls, half the reminder is 2s, half the reminder is 3s, and so forth. For example, an input of length 8 might look like [0, 0, 0, 0, 1, 1, 2, 3). See the interface. [9 points] Implement the method public Integer / generate Test Data HalfRandom (int size). Half the data is 0s, half random int values (use nextInt() from Java's Random package). For example, an input of length 8 might look like [0, 0, 0, 0, 54119567, 4968, -650736346, 1386 1 7093]. See the interface. [4 points] Each of these three techniques should be implemented as a method that takes an int representing the size of a dataset, and returns an Integer array containing that number of elements generated with the corresponding rule. Do not randomize (shuffle) the contents of the generated arrays. Using the three methods you implemented, develop and test hypotheses about the effect of input on the performance of insertion sort and shellsort. The code for these methods is already included in the base file for this assignment 1 . In a separate document (to be submitted as a PDF), write up your hypotheses (3 per algorithm): describe what you think the running time will look like (O(n)? O(n)? O(n)?) on each data set, and explain briefly why you think that. As long as your ideas make sense, and you do the analysis prior to benchmarking, you will receive full credit on the hypotheses. There will be a separate submission link on Canvas. 15 points] For each of the sorting algorithms, your program should run them on the three types of test data. Test them with datasets size of 4096 and 40962. (If your system is so fast that you don't get good results, you may increase the dataset size.) Time each of the tests with the Stopwatch class discussed in class. The program needs to compute the result of the doubling formula on the run times from the 2048 and 4096 result pairs to get the power ("b") for that algorithm on that type of input, and then display it. Six different values should be shown if you have properly implemented all of the benchmarks. Implement the method public double compute Doubling Formula (double 11, double 12). See the interface for more information. [12 points Implement the method public double benchmarkinsertion Sort(Integerd small, Integer/ large). See the interface for more information. [4 points] Implement the method public void run Benchmarks(int size). See the interface for more information. Hint: should call the two benchmark methods above. The output should look like below. [4 points] Insertion Shellsort Bin #### #### Half #### Ran Int #### 2 Requirements (36 points] For this assignment you will be writing code to generate test data and benchmark sorting algorithms on it (edited from Sed gewick and Wayne: 2.1.36). Already provided for you is BaseNon Uniform.java which con- tains the existing sorting algorithms. This class extends an interface called SER 222_02_01_HW02_Submission which defines all of the methods that you need to create. You may create additional private helper methods. First, write a series of methods to generate test data that is "non-uniform": Implement the method public Integerd generate Test Data Binary(int size). Half the data is Os, half 1s. For example, an input of length 8 might look like [0, 0, 0, 0, 1, 1, 1, 1). See the interface. [4 points] Implement the method public Integerll generate Test Data Halfs(int size). Half the data is 0s, half the remainder is ls, half the reminder is 2s, half the reminder is 3s, and so forth. For example, an input of length 8 might look like [0, 0, 0, 0, 1, 1, 2, 3). See the interface. [9 points] Implement the method public Integer / generate Test Data HalfRandom (int size). Half the data is 0s, half random int values (use nextInt() from Java's Random package). For example, an input of length 8 might look like [0, 0, 0, 0, 54119567, 4968, -650736346, 1386 1 7093]. See the interface. [4 points] Each of these three techniques should be implemented as a method that takes an int representing the size of a dataset, and returns an Integer array containing that number of elements generated with the corresponding rule. Do not randomize (shuffle) the contents of the generated arrays. Using the three methods you implemented, develop and test hypotheses about the effect of input on the performance of insertion sort and shellsort. The code for these methods is already included in the base file for this assignment 1 . In a separate document (to be submitted as a PDF), write up your hypotheses (3 per algorithm): describe what you think the running time will look like (O(n)? O(n)? O(n)?) on each data set, and explain briefly why you think that. As long as your ideas make sense, and you do the analysis prior to benchmarking, you will receive full credit on the hypotheses. There will be a separate submission link on Canvas. 15 points] For each of the sorting algorithms, your program should run them on the three types of test data. Test them with datasets size of 4096 and 40962. (If your system is so fast that you don't get good results, you may increase the dataset size.) Time each of the tests with the Stopwatch class discussed in class. The program needs to compute the result of the doubling formula on the run times from the 2048 and 4096 result pairs to get the power ("b") for that algorithm on that type of input, and then display it. Six different values should be shown if you have properly implemented all of the benchmarks. Implement the method public double compute Doubling Formula (double 11, double 12). See the interface for more information. [12 points Implement the method public double benchmarkinsertion Sort(Integerd small, Integer/ large). See the interface for more information. [4 points] Implement the method public void run Benchmarks(int size). See the interface for more information. Hint: should call the two benchmark methods above. The output should look like below. [4 points] Insertion Shellsort Bin #### #### Half #### Ran Int ####