Subject: Comments on the README
From: Kevin Chan (kachan@cs.washington.edu)
Date: Wed Apr 17 2002 - 09:06:28 PDT
I was going to write comments in you grade files, but they were all about
the same, that I felt one mass e-mail would have been better. If after
reading this, you feel that I graded your analysis incorrectly, please
come and talk with me during my office hours. It's getting rather lonely
there.
Finding Crossover Points
------------------------
The HW assignment asked you to find a crossover point and to draw some
type of conclusion from it. So here was what I was looking for.
* If you just gave me a crossover point with no justification as to where
that point came from, you lost points.
* If you provided a crossover point with justification, but no stated
conclusion about what this meant to you or in the scope of the algorithms
we have been discussing, then you lost points.
* For your conclusion, stating that in the long run one algorithm beats
the other, is not quite enough. That is very visible from the data. You
needed to provide some deeper analysis. Possible questions are:
-- Which algorithm would you use in practice? Is one better suited
for one set of data while the other is not?
-- Do these algorithms fit the expected running time we have been
discussing in class? Was it what you were expecting?
-- What are probably causes for why the crossover point is where
you found it to be? Could it be improved?
-- Did you notice any anomolies when you were gatherind data?
Any combination of answer to the above questions would have resulted in
full credit.
Extra Credit
------------
For the extra credit, if you wrote something, you got 1 point. To get more
points, you needed a deeper analysis. From looking at all of the answers,
many of you went into analysis of how each algorithm would before against
random vs. sorted arrays. This was good. Others evaluated the expected
running times and attempted to draw some conclusion from the data you
gathered. This was good as well. The deeper your analysis, the more points
you got.
Final Comments
--------------
First, I want to comment about the timing issues on the IWD clusters. The
crossover points should have been around 74 for Selection vs Shell, and
around 130 for Merge vs Insertion. If your numbers differed, I didn't take
points away. But there is a fundamental reason you need to be aware of.
When you call the timer functions, the timer functions are actually
reading a register on the PC that never changes. That's good. But you are
never guaranteed that your program will run to completion when you first
execute the program. Because UNIX and other OS are multi-process OS, that
means your program shares time with other programs. This means, you could
be running yours, and then after 2 us it gets swapped out. And not until
10us later does your program run again. This your time results are not
accurate. Some of you found this. The best way to handle this is to take
samples throughout the day or to gather data at the slowest time of day. I
did not take points off for this. This is just an FYI.
Second. When writing your README file, please put your full name,
assignment number, and date at the top.
Lastly, for those of you who did the extra credit. MergeSort actually
beats Quicksort. Only one person found the actual crossover point. Another
hypothesized about its location. So for small arrays (less than 1 million
or around this number) shell > merge > quick. For very large arrays
(greater than 1 million or about this number) shell > quick > merge.
This archive was generated by hypermail 2b25 : Wed Apr 17 2002 - 09:06:40 PDT