YCP Logo Lab 14: Reverse a List using a Queue

Due: Thursday, Nov 6th by 11:59 PM

Getting Started

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

Your Task

The task for this lab is the same as in Lab 13, with one exception: instead of using the get and set methods to reverse the elements of a List, use a Queue object to help you reverse the elements.

The idea is to transfer all of the elements from the list to the queue (removing them from the list), and then transfer them back from the queue to the list.

Important: Your algorithm should complete in O(N) time (where N is the number of elements in the list for both ArrayList and LinkedList objects.

Again, use the ReverseTest JUnit test class to test your method for correctness.

One your reversal method works, modify the Benchmark class's main method to benchmark running the method on both ArrayList and LinkedList objects with increasing number of elements. The loop increases the number of elements by 50,000 on each iteration.

As in Lab 13, output each data point in the format

numElements,arrayListTime,linkedListTime

Your output should look something like this:

500000,894,189
1000000,717,360
1500000,1073,544
2000000,816,645
2500000,1949,844
3000000,278,988
3500000,1410,1143
4000000,365,1267
4500000,1907,1400
5000000,3319,1862

Plot the data in Excel. Your plot should look something like this:

figures/lab14-benchPlot.png

Your guess is as good as mine regarding why the times for ArrayList are so erratic.

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

Submit

Make sure that you have included your Excel file in the project!

When you are done, save the project (CS201_Lab14) to a zip file by right-clicking it and choosing

Export...->Archive File

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

https://camel.ycp.edu:8443/