Lab 6
Empirical Analysis
February 23, 2006
Lab Partners
You may work with one partner on this in lab.
Objective
Recently, we have started analyzing code that we have produced
in lecture to determine its statement count and time complexity.
The purpose of this lab
is to help you learn how to conduct an empirical investigation
of an algorithm.
Before Starting
Create a BlueJ project named inlab6 and copy
the lecture code from Wednesday, February 22nd into it.
Insertion Sort Empirical Analysis: 10 points
Modify the code so that in one run (2 points), the program
measures and reports the total number of data comparisons and
the total number of swaps (the number of times that items
are shifted in the array)
for each of the following eight experiments. Printing the
initial data and the sorted data is unnecessary.
- Experiment 1: An array of 100 numbers arranged initially to
yield the best case.
- Experiment 2: An array of 200 numbers arranged initially to
yield the best case.
- Experiment 3: An array of 300 numbers arranged initially to
yield the best case.
- Experiment 4: An array of 400 numbers arranged initially to
yield the best case.
- Experiment 5: An array of 100 numbers arranged initially to
yield the worst case.
- Experiment 6: An array of 200 numbers arranged initially to
yield the worst case.
- Experiment 7: An array of 300 numbers arranged initially to
yield the worst case.
- Experiment 8: An array of 400 numbers arranged initially to
yield the worst case.
Write-up your results. In your report, include the following
information:
- A table that summarizes the results. 2 points.
- A description of what the best case data is.
1 points.
- A description of what the worst case data is.
1 point.
- A time complexity analysis of the results in the
table for the best case number of comparisons. 1 point.
- A time complexity analysis of the results in the
table for the best case number of swaps. 1 point.
- A time complexity analysis of the results in the
table for the worst case number of comparisons. 1 point.
- A time complexity analysis of the results in the
table for the worst case number of swaps. 1 point.
What to Submit
E-mail the modified code and report to your lab TA
in one message. The subject of the message
should be: CS221-xx inlab6 your-names.
The xx is the number of your lab section.
Before You Leave
Delete the inlab6 project that you created.
Empty the recycle bin. Thank you.