Parallel Algorithms: Difference between revisions
| Line 160: | Line 160: | ||
Assume Algo A is a "reducing algorithm"<br> | Assume Algo A is a "reducing algorithm"<br> | ||
We start with Algo A until the size is below some threshold. Then we switch to Algo B. | We start with Algo A until the size is below some threshold. Then we switch to Algo B. | ||
===Problem: Selection=== | |||
* Partition elements into rows of <math>\log n</math> size | |||
* For each row, find the median within the row | |||
* Find the median of medians (MoM) in <math>O(n)</math> | |||
* Put all rows with median <= MoM above and all rows with median >= Mom below | |||
* Now <math>m/4</math> elements are smaller and <math>m/4</math> are larger | |||
** Known as the reducing lemma | |||
==Resources== | ==Resources== | ||