in reply to Puzzle: The Ham Cheese Sandwich cut.

Perl Mouse,
I haven't started working on any of the challenges yet, because I wanted to raise a question first. When I learned about means, modes, and medians in statistics - I thought I remembered learnING that the median of an even list is the average of the two middle numbers. 
1, 2, 3, 4, 5, 6 = 3, 4 = 3 + 4 / 2 = 3.5

[download]
Is that correct? I guess it doesn't matter if it is since the line that bisects the two lists will still be the median.

Cheers - L~R

After posting the question, I realized that the answer doesn't matter. *shrug*

Replies are listed 'Best First'.
Re^2: Puzzle: The Ham Cheese Sandwich cut.
by Perl Mouse (Chaplain) on Nov 17, 2005 at 15:03 UTC
    It depends how you look at the problem. If you look at it as the 1-d variant of the "divide sets using a simplex" problem, any number between the two middle numbers will do. However, if you want to write a Quick Sort whose running time is garanteed to be O(N log N), you need to find a median in linear time, and you want to find an element of the set - not something in between.

    Wether you find one of the middle elements, or pick a number in between, I'll accept both solutions. ;-).

    Perl --((8:>*
[reply]

      Are you sure in this? Once you have found a number so that exactly half of the numbers are to the left and half are to the right, couldn't you separate these two classes of numbers, sort them separately, and still get an O(N log N) time sort this way?

      If I have to define median, I'd say that if you have an even number of data, any number between the two middle one is a median. This way the definition is equivalent then if you say that the median is a number whose total distance from the given numbers is minimal. This latter definition has paraleles: the mean is the number for which the square sum of its distance from the given numbers is minimal. More clearly, given the sequence (x_1, ..., x_N), the mean is the number A that minimizes the expression |x_1 - A|^2 + ... + |x_N - A|^2; the median is M if it minimizes |x_1 - M| + ... + |x_N - M|. Furthermore, informally speaking, the modus C minimizes |x_1 - C|^epsilon + ... + |x_N - C|^epsilon, where epsilon is a very small positive number.

[reply]
        Are you sure in this? Once you have found a number so that exactly half of the numbers are to the left and half are to the right, couldn't you separate these two classes of numbers, sort them separately, and still get an O(N log N) time sort this way?
        Well, yes, that is the point. However, to archieve this, you 1) must divide the set into pieces in linear time and 2) each subset must contain at least cN numbers, for some 0 < c < 1. Using the median as the pivot to divide the set satisfies condition 2), but to satisfy condition 1), you need to find the median in linear time.
        Perl --((8:>*
[reply]

In Section Meditations