Spring 1996
Assignment 10, due Tuesday April 30 at 2PM
No Late Assignments Will Be Accepted.
In this final assignment, you will:
- Implement the sorting routine of your choice
- Compare performance of your sorting routine with that
of qsort for large, randomized datasets of various sizes.
Correctness Testing
To test the correctness of your sorting routine, you must choose a
small (n about 20) set of randomly chosen data and then sort the data
using each routine on that set. Turn in the dataset and the output of
your routine on that set.
Performance Testing
For both your sort and qsort, characterize the average
CPU time used and the average number of comparisons made.
To do this, your program must generate large data sets of randomly
chosen numbers and run qsort and your sort routine. Choose
at least five different sizes (such as n=1000, 2000, 3000, 4000,
5000). Measure the average CPU time used and the average number of
comparisons made for each size of n. Take the average performance
over 100 trials at each size n.
Make sure that dataset size is large enough so that the time used
clearly grows with n, but not so large that you swamp your memory or
that it takes inordinately long (so the range of n used very much
depends on which machine you use).
While doing your programming assignment, you should also think about
the complexity of the sorting algorithm you implement.
What You Turn In
For this assignment you will not do electronic submission.
Instead you must hand in a printed report that includes:
- A written description of what your program is doing along with a
discussion of the complexity of sorting algorithm that you
implemented.
- A well documented source code of all your program including header
files, program code, main test driver, etc. The code you submit should
conform with the program assignment
guidelines.
- A test result printout that shows the correctness testing of your
program.
- A graph plotting average CPU times for both qsort and your sort
as a function of data set size. This should allow for direct comparison
of qsort vs. your sort.
- Another graph plotting average number of comparisons for both qsort
and your sort as a function of data set size. Again t
his should allow for direct comparison of qsort vs. your sort.
Extra Credit
Extra credit will be given for anyone who can develop a sorting
routine that has average performance better than qsort
for large n. Your routine should on average
provide fewer comparisons and/or less CPU time for randomly
generated test datasets.
If you successfully complete the extra credit,
explain how you did it in your report. You must also
electronically submit your code in the usual way.
No Late Assignments Will Be Accepted
Programming assignments are due before the last class.
Academic Honesty and Collaboration
It is reasonable to discuss with others possible general approaches to
problems. It is unreasonable to work together on a detailed solution,
to copy a solution, or to give away a solution. If your common
discussion can be detected by looking at the solutions, then there is
too much collaboration. Such instances of academic dishonesty will
result in a course grade of F or expulsion from Boston University.
Do not allow your work to be used by others:
- Set the permissions so that they are not readable by others.
- Do not recycle old printouts. Take them home to throw them out.
- Do not e-mail your solution to anyone.
Warning: If someone cheats by using your work, you will also be penalized
Page Created: April 17, 1996
Maintained by: Stan Sclaroff