This assignment asks you to time a set of operations on two implementations of the java List interface. You will need to describe the big-Oh run-time of these operations and discuss if your experimental results support the big-Oh run-time. To plot your results, you will be using the common linux plotting program gnuplot. You should save your programs in your cs35/homework/05 directory. For this assignment, you should work by yourself.

You will create your graphs with gnuplot — a common and relatively easy plotting tool for linux. A number of tutorials can be found online. While gnuplot can be used in an interactive way, it can also be scripted. I typically use the interactive screen to setup my plot and then script a solution that contains my common settings.

A sample gnuplot script might look like this. This text was saved in the file gplot

set terminal png large size 800,600
set output "tmp.png"
plot "results" using 1:2 title 'array list', \
  "results" using 1:3 title 'linked list' lt 3

This code plots two lines. The first line uses columns 1 and 2 of the file results as the x and y coordinates, respectively. The second line uses columns 1 and 3. The results is a space separated list of numbers. The first few lines are shown below.

99990 116.0 1627.0
99889 118.0 1625.0
99788 115.0 1624.0
99687 119.0 1622.0
99586 115.0 1623.0
99485 118.0 1626.0
99384 116.0 1624.0
99283 120.0 1620.0
99182 127.0 1622.0
99081 121.0 1619.0

To run the script, type gnuplot gplot at the terminal. The output will be saved in tmp.png. You can view this file in firefox or the gimp. You can either modify the gnuplot script to save to a different file or use mv or cp to move or copy tmp.png to a more suitable name. For each of the following experiments, create a plot showing the runtime of operations for varying input sizes. In each experiment, choose an appropriate range of input sizes to test. As a general rule of thumb, each experiment should run between one and five minutes. You may need to adjust the input size depending on the run time to hit this target.

In the first set of experiments, create plots that compare the LinkedList and ArrayList implementations of the Java Collections Framework List interface. You may build a list on any object type (Integers are fine, but feel free to try something else too). The operations you time must include.

• add(0, el) - add element to front of list
• add(n/2, el) - add element to middle of list
• add(n, el) - add element to end of list
• remove(0, el) - remove element from front of list
• remove(n/2, el) - remove element from middle of list
• remove(n-1, el) - remove element from end of list
• get(0) - get element from front of list
• get(n/2) - get element from middle of list
• get(n-1) - get element from end of list

In the second set of experiments compare the ArrayIndexList performance to the ArrayList to three of the above operations. Your selection should include at least two operations from the set {add, remove, get} and at least one O(1) and one O(n) operation.

Along with your java source code, you should hand in a README file, png images of all your graphs and your Makefile if you used one. These files will be imported automatically via handin35. In your README file, discuss briefly the expected big-Oh notation of each of the operations listed above and discuss how the experimental results agree or disagree with the big-Oh complexity. If you notice any interesting effects, please note them in your readme. For each operation, please note which .png file shows the plot for that operation.

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:42 AM