Randomized Algorithms (Spring 2010)/Tail inequalities: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop No edit summary |
imported>WikiSysop |
||
| Line 3: | Line 3: | ||
The [http://en.wikipedia.org/wiki/Selection_algorithm selection problem] is the problem of finding the <math>k</math>th smallest element in a set <math>S</math>. A typical case of selection problem is finding the '''median''', the <math>(\lceil n/2\rceil)</math>th element in the sorted order of <math>S</math>. | The [http://en.wikipedia.org/wiki/Selection_algorithm selection problem] is the problem of finding the <math>k</math>th smallest element in a set <math>S</math>. A typical case of selection problem is finding the '''median''', the <math>(\lceil n/2\rceil)</math>th element in the sorted order of <math>S</math>. | ||
The median can be found in <math>O(n\log n)</math> time by sorting. There is a | The median can be found in <math>O(n\log n)</math> time by sorting. There is a linear-time deterministic algorithm, [http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22 "median of medians" algorithm], which is very sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time. The idea of this randomized algorithm is based on sampling. | ||
=== Randomized median algorithm === | === Randomized median algorithm === | ||
=== Analysis === | === Analysis === | ||
== Chernoff Bound == | == Chernoff Bound == | ||
== Permutation Routing == | == Permutation Routing == | ||
Revision as of 03:15, 25 January 2010
Select the Median
The selection problem is the problem of finding the [math]\displaystyle{ k }[/math]th smallest element in a set [math]\displaystyle{ S }[/math]. A typical case of selection problem is finding the median, the [math]\displaystyle{ (\lceil n/2\rceil) }[/math]th element in the sorted order of [math]\displaystyle{ S }[/math].
The median can be found in [math]\displaystyle{ O(n\log n) }[/math] time by sorting. There is a linear-time deterministic algorithm, "median of medians" algorithm, which is very sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time. The idea of this randomized algorithm is based on sampling.