One of my students in my Algorithm class gave a simple and interesting answer to an exercise of the textbook "Introduction to Algorithms" (3rd ed.), much different from most solutions given in the Internet. The exercise is 8.4-4 as follows:
"We are given n points in the unit circle, pi = (xi, yi), such that for i = 1, 2, . . ., n, such that 0<x1^2 + y1^2<=1. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design an algorithm with an average-case running time of Theta(n) to sort the n points by their distances from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)"
As you may see, most "standard" solutions are: split the distance at sqrt(i)/sqrt(n). However, this student raised another simple and interesting solution: simply split the distance evenly, that is, at 1/n. The justification of this solution is as follows:
"You will see the areas of regions are: (i^2-(i-1)^2)/n^2 = (2i-1)/n^2. The largest bucket (the outermost) has an averaged size: (2n-1)/n <= 2. So, the average-case running time is still Theta(n)."
I sent the solution to the authors, and Prof. Cormen answered the following (May 25th, 2013):
... I believe that you are correct. Of course, the solution your student developed is also interesting and makes the problem even more interesting since the simple solution works, too.
We'll think about what to do with this exercise for the next edition of the book.
Tom Cormen
It is nice to know that the authors would take this into consideration in the next edition.
I-Chen Wu
