Lab 11

Stress Tests

Goals: The goal of this lab is to illustrate on concrete examples and experiences the differences in the time complexity of algorithms.

Homework assignment for this week includes finishing anything you did not finish during the lab and turn in your results.

Getting started

Create a new project. Download the following files:

student.zip

Lab11.zip

Unzip student.zip and import the whole folder you get (named student) into your project. (Alternately, define a new Package named student, highlight it, and import the files in the student folder into it.

Unzip Lab11.zip. Add sorting.jar, jpt.jar, and tester.jar to the classpath for your project. Finally, save the file citydb.txt in the same directory in your EclipseWorkspace where the src and bin files are stored for this project.

Your project should be ready to run, but we will wait with that.

Note: The files in the student.zip file are saved in a folder named student. You have to import the whole folder into Eclipse. It will show up as a new package in your project.

Notice that both files in this package start with the declaration package student;. This is the way Java programming language allows you to combine together classes that belong together and form a comprehensive collection that can then be turned into a library.

Run the project using the TimerTests class as the class that contains main, to make sure you have all pieces in place. When the File Chooser Dialog comes up select the file citydb.txt.

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 define the ordering of the data. When you run the program, the time that each of these algorithms took to complete the task is shown in the console.

Question: How many timing results would you collect if all of these tests rans successfully?

Set up a new Run Configuration where you select the class sorting.Interactions as the main class. Run the program. It will come up with a GUI with several buttons. You need to use them in the correct order:

• Start with File Input button. It opens the File Chooser Dialog and when you select the file citydb.txt it reads in the data for the 29470 cities.

• Next 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 that you have designed. The two files in the
  student
  package originally provided only hooks to the stress test program — the method heapsort in the class Heapsort, so you could run the stress tests even if you did not implement the heapsort algorithm. The original stub just returned the original unsorted ArrayList. So, if you are having difficulties with finishing the implementation of the heapsort, leave it for now, and run the program with the original files in the student package.

• In the third step, (once you read in the data and have chosen which algorithms to run, for which data set sizes, and with which Comparators), you can run the actual timing 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 as a part of the Assignment 11.

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(n^2)?

• Which algorithms run mostly in O(n.log_n) 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.

Note: The following algorithms are included in the choices: binary tree sort; insertion sort (2 versions); merge sort; quicksort (2 versions); selection sort. See if you can figure out which one is which.