CSC 205Java Programming II10/21/2018

Lab 13

Runtime Analysis

In this lab, we will practice

-Generating random datasets using the java.util.Random class

-Writing driver classes to conduct runtime experiment

-Measuring real runtimes using the currentTimeMillis method of theSystem class

Part I – Generating Random Datasets

  1. Sample code 1: RandomDataset.java
    Copy sample code files from the lab14 folder to your own folder. Create a new project named lab14(using the Project Manager) and open source files (under your own directory) individually to mount them in the IDE’s filesystem.
    Read RandomDataset.java. In the generateDataset method, use the following statement to replace the one that sets every element to 0. The nextInt method returns a random integer every time it is invoked.
    dataset[i] = rnd.nextInt();
    Compile and execute RandomDataset.java. You can see the numbers in the dataset appear to be random. If the two passes generated identical datasets, run the program again to convince you that a Random object can be used to generate apparently random sequences, each time starting with a different number.
    Sometime it makes sense to use identical datasets to exercise different algorithms with to compare their performance. In those circumstances, one can instantiate a Random object with a seed, e.g.
    Random rnd = new Random(seed); // e.g., seed = 2004;
    Uncomment the second half of the main method and execute it a few times to convince yourself that generateDatasetthat takes an additional seed parameter returns the same set of data for the same seed value.
  2. Enhancement 1: modify the RandomDataset class so that it can generate a set of data whose values fall in a given range, such as 0 to 9999.
    Overload the generateDataset method with a new version that takes a minimum value and a maximum value in addition to the size parameter. You may duplicate the old version and modify it. Calculate the span of the required range and generate the values using the following statements:
    int span = max - min;

dataset[i] = min + Math.abs(rnd.nextInt()) % span;

Conduct a few experiments of generate integers ranging from 0 to 9999. Save your result to the lab report.

Part II – Tree Height Hypothesis

Suppose you want to perform a run-time experiment to support the claim that the average height of a binary search tree is logarithmic in n, where n is the size of the tree. Here is one way to proceed. Conduct 20 trials. In each trial, anIntTreeBag of n random ints is generated and the height of that tree is calculated. After the last trial, the ratio of the average height to log2n is printed. Suppose this ratio does not change much for successively larger values of n (say, by doubling n four times, with 20 trials each time). Then that should improve your confidence that the average height of a binary search tree is, indeed, logarithmic in n.

In this part, we’ll use the IntTreeBag class (backed by the IntBTNode class) to generate BSTs and write a test driver class, TreeHeightTest.java.

  1. Enhancement 2: thetreeHeightmethod
    Complete the code needed for the heightmethod of the IntBTNode class that calculates the tree height. The logic is illustrated as follows:
    if (t is empty)
    height(t) = 0;
    else
    height(t) = 1 + max(height(t.getLeft()),
    height(t.getRight())
    Debug and test your new method with the simpleTest method in TreeHeightTest.java.
  2. Sample code 2: TreeHeightTest.java
    Compile and execute the TreeHeightTestclassand record the average tree heights and the corresponding log2n values. Pay special attention to the following code segments:
    Random rnd = new Random((int)(SEED*Math.random()));
    // in generateDataset, enforces a different seed is used
    ...
    Math.log(size)/Math.log(2)
    // in printHeights, converts 10-based log to 2-based
  3. Enhancement 3: TreeHeightTest.java
    Modify the TreeHeightTest class so that it uses the generateDatasetand the printDatasetmethods in your RandomDataset class.
    Replace the outer for loop with while(true), such that the program will terminate only when the dataset is too big to fit in the main memory on your desktop.

Part III – Linear and Logarithmic Runtime

We’ve learned that basic operations, such as searching, removing, on a BST is logarithmic to dataset size nyet is linear on an unsorted list. In this part, we’ll create BSTs and lists with the same datasets and compare runtimes for removing elements in the datasets. We’ll create trees in the same way as in Part II, and create lists using the IntLinkedBagclass (backed by IntNode).

  1. New class: RuntimeTest.java.
    You may start from making a copy from TreeHeightTest.java and modify the source code. (Or you may modify the RunTimeTest.java file, see below) Here is a list of features you need to add or replace:

-a variable for list in the type of IntLinkedBag

-replace heights with runtimes, which is a two-dimensional array or use two one-dimensional arrays, one for lists and one for trees

-invoking a getRuntimes method (to be added), instead of invoking the height method

-implement a overloaded getRuntimes method, one version for trees, and one for list

Here is a sample implementation of the getRuntimes methodfor trees:

private static long getRuntime(IntTreeBag tree, int[]
dataset, int[] indexes) {

long time0 = System.currentTimeMillis();

for(int k=0; k<1024; k++) {

for (int i=0; i<indexes.length; i++) {

tree.remove(dataset[indexes[i]]);

}

}

return System.currentTimeMillis() - time0;

}

The array indexes is used to conduct multiple (10 as used in the sample code) removals so that the time used can be measured. For trees, this process has to be repeated about 1000 times (notice the for loop for k varying from 0 to 1024) so that the time used may be sensed. (This loop is not needed in the list version.) You may use the generateDataset method that specifies a value range to create indexes.
(If you are modifying the TreeHeightTest.java file given in the lab, modify it by using appropriate versions of thegenerateDataset method in your RandomDataset class.)

Execute the test program a few times and plot the runtimes for trees and lists against log2n.

Deliverables

Ftp your source code files to and appropriate directory under your Cobra account. Turn in the completed report with supporting raw data, as well as your analysis on tree height and runtimes by Tuesday11/30.

Lab13-1