CS14 - At-Home Programming Assignment 4

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 5% 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 a single ps or pdf file. Do not include seperate jpg files for you graphs. You must embed them into your ps or pdf file. If you use LaTeX, make sure to create the ps or pdf file before submitting your report.
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 using time(1) (see hint below).
The sorting executables sort whitespace seperated positive integers. You must create your own test files to sort. A sample test file is here however your test files should be much, much LARGER. You supply your test file to the sorting executable via input redirection (i.e. type "sort1 < testfile.txt"). Google for input redirection for more information. The execution will output the sorted integers to the screen. You may use output redirection to capture this info (Google for output redirection)

Extra Credit

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

5% 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. Please use the man and info pages or Google.

A reminder about collaboration on home programming assignments

Please remember, at-home programming assignments are not lab assignments and you may not team-code with your lab partner or any other individual. Limited collaboration may be acceptable, but programs must represent YOUR OWN original work. Sharing code or team-coding are strictly not allowed (even if team-coding was acceptable in a previous class, this course DOES NOT allow team-coding). Copying code from ANY source (any book, current or past students, past solutions, web, etc) is strictly not allowed even with citation. Collaboration may consist of discussing the general approach to solving the problem, but should not involve communicating in code or even pseudo-code. Students may help others find bugs. Your code MUST be unique -- the odds of randomly producing similar code is very low. Computing, like surgery or driving a car or playing golf, can only be learned by doing it yourself!