Lab 8
Lab 8 Description
Preamble
Before the end of the first year when our students think they are becoming competent programmers, we want to make sure that they are aware of the true meanign of algorithm complexity. Talking and writing down formulas has little meaning in the age of lighning-fast internet.
So, we ask them to run several different solutions to the same problem and observe the differences in the time needed to complete the task.
Work on this lab, and see if we manage to help students think about this issue.
StressTests - Timing Tests
Your job is now to be an algorithm detective. The program we give you allows you to run any of the six different sorting algorithms on data sets of five different sizes using three different Comparators to produce the ordering of the data based on the given Comparator.
When you run the program, the time that each of these algorithms took to complete the task is shown in the console.
To run the program you need to do the following:
Create a new Java Project (e.g. SortingTests).
Download the file StressTestFiles.zip and unzip them.
Add the file sorting.jar and jpt.jar to the project’s classpath.
Create a new Package in Eclipse and give it a name student. Import into this package the two files: SortingHeapSort.java and Heapsort.java.
Download the file citydb.txt and save a copy in the Eclipse directory that has the src and bin directories for the SortingTests project.
Go to the Run menu, choose Run Configurations, select to make a new configuration. Name it SortingTests then click on the button to Select main. One of the choices should be sorting.Interactions. Choose that one.
You can now run the program. It will come up with a GUI with several buttons.
To set up the timing tests you need to go through three steps:
First you need to read in the data for the 29470 cities from the file citydb.txt. The button FileInput opens a file chooser dialog. Select the citydb.txt file.
Now hit the TimerInput button. It lets you select which algorithms to test, which Comparators to use, and what size data should be used in the tests.
Start with just a few small tests, to see how the program behaves, before you decide to run all tests.
The last choice is heapsort. The two files in the student package illustrate the design of the hooks to the stress test program. For our students the method heapsort in the class Heapsort just returns the original unsorted ArrayList and our students are asked to implement this algorithm. We provide the solution to show you how the different sorting algorithms are invoked from the project code.
Now you can run the actual tests by hitting the RunTests button. You can repeat the last two steps as many times as you want to.
Exploration
Spend about fifteen minutes trying to answer some of the following questions. Finish the work later. (We ask our students to finish this at home.)
Run the program a few times with small data sizes, to get familiar with what it can do. Then run experiments and try to answer the following questions:
Which algorithms run mostly in quadratic time, i.e. O(n2)?
Which algorithms run mostly in O(n.logn) time?
Which algorithms use the functional style, using Cons lists?
Which algorithm is the selection sort?
Why is there a difference when the algorithms use a different Comparator?
Copy the results into a spreadsheet. You may save the result portion in a text editor with a .csv suffix and open it in Excel (or some other spreadsheet of your choice). You can now study the data and represent the results as charts. Do so for at least three algorithms, where there is one of each — a quadratic algorithm and a linear-logarithmic algorithm.
Produce a report with a paragraph that explains what you learned, using the Excel charts to illustrate this.