CS 14 - Sorting Report

Your assignment is to perform some experimental testing on a set of programs provided to you to determine the Big-O running time of the programs. You will need to write a report describing your experimental methods and your final conclusions. You may earn up to 20% extra credit for turning in your report in LaTeX.

Requirements

This is a lab science report. Everything you've ever learned about how to do lab science applies, and everything you should have learned applies as well. A few things to keep in mind:

Your report must be submitted in .txt, .ps, or .pdf format.
Your report must be as long as it needs to be to prove your claims.
You must measure the rate of growth of the runtimes of the programs, absolute measurements of speed mean nothing.
All numeric values in your report should include proper units.
A single experiment doesn't prove much. Multiple runs of the same experiment should be used. Don't underestimate the time this data collection will take.
Where and when you take the data is important. If you are running the experiment on one of the CS department machines, it would be best to note who else (if anyone) is on the machine while you are taking data. This will require you to learn a new Unix command or two.
Your eyeball doesn't say much. When you have a series of data, it is best if you can use function-fitting software (such as that in gnuplot, matlab, or mathematica) to find out whether your function fits an n log n curve better than n.
A full credit report will likely include graphs of the run times, tables of function fits, and final conclusions.
Time your programs the same way we did for the Anagrams assignment at the beginning of the quarter.

Extra Credit

20% extra credit is available for reports generated in LaTeX.

10% extra credit is available for reports that contain proper error analysis.

Downloads

Here are the executables (compiled under Linux):

Hints

The time(1) utility under Linux may be useful. You may also want to investigate gnuplot. Titus will be happy to explain either of these tools.