You are to devise an experimental design for testing and analyzing the O() running time of a sort discussed in class.

We claim to know how long the three sort algorithms from Chapter 3 and one sort from Chapter 5 will take (for some N and some "condition" of the data). Design a set of experiments using the Scientific Method for testing your hypotheses (for all four sorts) of the O() running time. Any science prof, book on experimental design, your old science fair guide, ... should refresh your memory on the REQUIRED steps in the Scientific Method.

Your paper will describe your experiment and the results

• Clearly state the hypothesis
• Describe your experiment
• Must be repeatable
• Note that you must include the actual algorithm used, not simply state its name (Bubble? Which one?)
• What are your variables?
• What control set did you use?
• Results?
• Analysis?
• Conclusions?

Program considerations

• Test algorithms using small N for correctness
• Use the same data for each of the three sorts
• Large N (Do you need to vary N?)
• Keep in mind that you can’t control what else is going on during a particular program execution on a typical workstation
• Java program must time an operation accurately
• Work in teams of 2-4
• Split the work, but all are involved in all aspects

1. Introduction
   Begin your paper by fully describing (with references) your experiment
2. Background
   Describe the research methodology that you used, the refernces that you analyzed and evaluated, and any other requisite knowledge that a sophomore in computer science would need to understand your experiment, results, and conclusions
3. Experimental Design. Sub-sections should be considered here for
   each step taken
   issues encountered

   Results and Conclusions

Technical Requirements

• 12pt Calibri font, 1.5 spacing with normal
• Headings - 14pt font
• Full justification (even on left and right edges)
• Paragraph indentation 1/4 inch
• title page (not included in the page count)
  Title
  Authors
  16pt font
• FIVE (for the draft) and EIGHT (for the complete paper) pages of writing
• 8 full pages (not including title page, bibliography, and figures/diagrams)
• approximately 2000 words
• Pictures, drawings, ... are encouraged but not part of the page count
  If you have two pictres each using 1/2 page, then 1 page is subtracted from the count
• Every direct quote must be cited immediately after using [ ] with the author's name. If you are citing two or more works by the same author, follow the author's name with 1, 2, ... signifying which reference in the bibliography you are referring to.
• Bibliography must be sorted by author's names