Abstract: This course is greatly concerned with characterizing
the performance of a given approach or algorithm. In this lab, you measure
the time of appending to two different
implementations of the List ADT: one has tail reference,
and other does not.
Goals of this lab:
To appreciate that a simple change to a data structure can have a dramatic
effect on performance.
To appreciate that the concepts we study in theory, namely
asymptotic time complexity,
is actually observable in practice.
Warmup procedure
For this lab, you should have access to a platform with the following:
Java 8
Excel
Update your repository to make sure you have the most recent software checked out.
Right (control) click on your project name in the package explorer
Drag down to Team
Choose Update
Your work for this lab
In the labs source folder, in the lists package,
open the ListExperiment class.
Run that class as a Java Application and it will append
two experimental runs to the linkedlist.csv file in the
output folder.
Open linkedlist.csv using Excel and plot the No Tail
and With Tail, with run times plotted
against input size.
At this point, the two curves should be fairly similar.
In the labs source folder, in the lists.links
package, open the LinkedListsWithTail.
Add a tail reference to that class, and make sure it always
references the last element in the list.
Appending to the list should now be done in LinkedListWithTail
using the tail reference, rather than iterating through the
list to find its end.
Rerun the ListExperiment, and plot the resulting data (found at the end of the linkedlist.csv file.
You must save the resulting plot in the outputs folder.
The plot won't save in a csv file
So instead, right (control) click on the plot and save it as a picture
named linklist (.jpg or whatever) in the outputs folder.
How to submit your work
Make sure all of your work is commited and PUSHED in your repository.
Your work will be graded as of the due date for this assignment.
Submitting your work (read carefully)
You must commit all of your work to your repository and push it. It's best to do this
from the top-most level of your repository, which bears your wustl key.