Communications of the ACM
Not Your Grandmother's Textbook Exercise
In my eulogy of Barry Boehm last week in this blog, I mentioned from memory an exercise in his classic Software Engineering Economics textbook (Prentice Hall, 1981). Now I've got my hands on the book itself and found that it is even better than I remembered. So here is the exercise text in its entirety. It is exercise 1.4, page 9. I hope that citing one exercise from a 1981 textbook, even in full, falls under fair use.
They do not write textbooks like this anymore!
<Boehm Software Engineering Economics exercise quote>
Mary Jones in the Accounting Department tells you that she has a file of personnel records [2022 update: an Excel sheet] and asks you to develop a program to compute the median age of the personnel in the file. Here are four different ways you might respond:
(a) Invoke a sort routine which sorts the personnel file by increasing age. Count the number, N, of personnel records in the file. Find record N/2 in the sorted file. Rxtract its value for "age".
(b) Note that in The Art of Computer Programming [Knuth, 1973], Vol. III, pp. 209-220, the problem of obtaining the median is a special case of the problem of finding the ith largest of N numbers, and that R.W. Floyd has formulated a recursive method of obtaining the median in an average of 3/2 N + O (N2/3 log N) comparisons. Spend a couple of weeks attempting (unsuccessfully) to improve on Floyd's algorithm, a day programming Floyd's algorithm, and then return to Mary Jones with some questions on the size and format of her file.
(c) Ask Mary how soon she needs the results, how much she is willing to pay for them, how many records, N, her personnel file has, and how often she will be making such runs. If N is large, and she wants results often, quickly, and cheaply, ask her if she would be satisfied with the mean value, which is much easier and cheaper to calculate. If not, work with Mary to tailor an approach to obtaining the median which is the best compromise between her various objectives.
(d) Compute the mean age, and print it out as the median. It's much easier to program, and Mary Jones will probably never notice the difference.
Rank the responses in the order of their relative concern with programming considerations, economic considerations, or other important considerations. If you were the programmer, which approach would you prefer? If you were Mary Jones, which approach would you prefer?
</Boehm Software Engineering Economics exercise quote>
Bertrand Meyer is a professor at the Schaffhausen Institute of Technology (Switzerland) and chief technology officer of Eiffel Software (Goleta, CA).
Comments
Willy Lai
(e) Use bucket sort, assuming age [0..150], and retrieve the median in O(N).
Displaying 1 comment