Apparently, an unscientific search brings up CSA 464 taken at Miami University (Ohio), course on algorithms of course... but I'm trying to find the professor. I had a professor once that was similar to this one, though not as brash... CS prof that was diligent about spelling and the correctness of English prose and/or phrases. In several homeworks and exams I pointed out fallacies in his questions- but again, nothing comical though like this one.
I don't know if the student was "brave" so much as "did not know how to demonstrate that you cannot find the median of an unsorted list without examining every item in the list".
A quick and fairly informal sketch of the proof: here's a three element list: 1, 2, N. If you tell me which of those three is the median without known N, then I can always surprise you with an N such that your guess is wrong (you guess 1 or 2, surprise, N was 0. You guess N, surprise, N was -1).
Now append negative MAX_INT and positive MAX_INT to the list.
The size of the list is now 5, and the median must be either 1, 2, or N. Care to take a guess prior to me revealing N? Whoops, looks like you lose again.
We can keep playing this game for any size of list you want to play with greater than zero: for any size of list I can create at least one list such that not knowing one number makes the median unknowable. (I could show you for an even number of elements, too, but won't for brevity.)
Thus, since you can't calculate the median of a list in less than O(n), you can't use "calculate the median and..." in any procedure you claim has a big-O complexity less than O(n).
Thought this would be much more HN-y if there was a prospect of the problem actually mattering in the real world, rather than being a pair of poor jokes on a CS exam.
6 comments
[ 3.2 ms ] story [ 30.3 ms ] threadApparently, an unscientific search brings up CSA 464 taken at Miami University (Ohio), course on algorithms of course... but I'm trying to find the professor. I had a professor once that was similar to this one, though not as brash... CS prof that was diligent about spelling and the correctness of English prose and/or phrases. In several homeworks and exams I pointed out fallacies in his questions- but again, nothing comical though like this one.
A quick and fairly informal sketch of the proof: here's a three element list: 1, 2, N. If you tell me which of those three is the median without known N, then I can always surprise you with an N such that your guess is wrong (you guess 1 or 2, surprise, N was 0. You guess N, surprise, N was -1).
Now append negative MAX_INT and positive MAX_INT to the list.
The size of the list is now 5, and the median must be either 1, 2, or N. Care to take a guess prior to me revealing N? Whoops, looks like you lose again.
We can keep playing this game for any size of list you want to play with greater than zero: for any size of list I can create at least one list such that not knowing one number makes the median unknowable. (I could show you for an even number of elements, too, but won't for brevity.)
Thus, since you can't calculate the median of a list in less than O(n), you can't use "calculate the median and..." in any procedure you claim has a big-O complexity less than O(n).
Thought this would be much more HN-y if there was a prospect of the problem actually mattering in the real world, rather than being a pair of poor jokes on a CS exam.