Re:Helping a stranger, and why you should understand NP-comp...
by ggchappell on Monday November 04, 2013 @05:02PM
(#6671498)
I'm familiar with the median-of-medians linear-time selection algorithm (a.k.a. BFPRT). But I don't recall ever seeing a construction of a pivot-finding algorithm using de-randomization. Do you have a reference for this?
Re:Helping a stranger, and why you should understand NP-comp...
by eru on Tuesday November 05, 2013 @12:15AM
(#6673353)
Sorry, that was from memory. (Can't you interpret the BFPRT as a de-randomization?)
Anyway, slightly modified my point still stands: BFPRT is way more complicated (and harder to come up with) than randomized QuickSelect.
If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.