Getting Started

Download CS201_Lab12.zip. Import it into Eclipse (File→Import...→Existing Projects into Workspace→Archive File.) You should see a project called CS201_Lab12 in the package explorer.

Your Task

Your task is to benchmark removing all elements from an ArrayList using two techniques:

  1. Repeatedly remove the last element
  2. Repeatedly remove the first element

Start by stating a hypothesis. How will the running time of each of these techniques increase as the number of elements in the array list increases?

Open the file hypothesis.txt in the project and write down your hypothesis. Be specific about how the running time of each algorithm will increase as the number of elements increases.

Test your hypothesis. Test both of these techniques on a series of ArrayLists containing increasing numbers of elements. Start at 10,000 elements, and increase by 10,000 elements up to 100,000 elements.

State your conclusion. After you have tested your hypothesis experimentally (as described below), edit hypothesis.txt to state your results. If your experimental results did not match your hypothesis, explain why.

Experiment

You can use the following method to create ArrayList objects with a specified number of elements:

public static ArrayList<Integer> create(int count) {
    ArrayList<Integer> a = new ArrayList<Integer>(count);
    for (int i = 0; i < count; i++) {
        a.add((Integer) 42);
    }
    return a;
}

You can measure the number of milliseconds required to execute a block of code as follows:

// force a garbage collection
System.gc();

long start = System.currentTimeMillis();

// ...code that you want to benchmark...

long end = System.currentTimeMillis();

long elapsed = end - start;

Important: run your benchmark on the ArrayList class included in the lab, not the built-in java.util.ArrayList class.

Output and Analysis

The output of the program should be a series of lines of comma-separated values:

Your output should look something like this:

10000,xxx,yyy
20000,xxx,yyy
30000,xxx,yyy
40000,xxx,yyy
50000,xxx,yyy
60000,xxx,yyy
70000,xxx,yyy
80000,xxx,yyy
90000,xxx,yyy
100000,xxx,yyy

xxx and yyy are the number of milleseconds to remove all of the elements for each of the two techniques.

Once you have collected your benchmark data, import it into Excel (you should be able to simply select the output of your program, copy it to the clipboard, and paste it into Excel). Plot the data (second and third columns), using the first column as the X-axis.

Copy your Excel file into the Eclipse project. (Put it in the subdirectory of your Eclipse workspace called CS201_Lab12, and in Eclipse right-click on the project and choose Refresh.)

Submitting

When you are done, submit the lab to the Marmoset server using either of the methods below.

Make sure that you close Excel before attempting to submit the lab.

From Eclipse

If you have the Simple Marmoset Uploader Plugin installed, select the project (CS201_Lab12) in the package explorer and then press the blue up arrow button in the toolbar. Enter your Marmoset username and password when prompted.

From a web browser

Save the project (CS201_Lab12) to a zip file by right-clicking it and choosing

Export...→Archive File

Upload the saved zip file to the Marmoset server as lab12. The server URL is

https://cs.ycp.edu/marmoset