Randomized Algorithms (Spring 2010)/Tail inequalities: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Select the Median == 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…'
 
imported>WikiSysop
No edit summary
Line 8: Line 8:


=== Analysis ===
=== Analysis ===
== Chernoff Bound ==
== Permutation Routing ==

Revision as of 08:54, 22 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 sophisticated deterministic algorithm, "median of medians" algorithm, which finds the median in [math]\displaystyle{ O(n) }[/math] time. 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

Analysis

Chernoff Bound

Permutation Routing