Selection Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 20: Line 20:
{{External|https://www.coursera.org/learn/algorithms-divide-conquer/lecture/obhKq/randomized-selection-analysis}}
{{External|https://www.coursera.org/learn/algorithms-divide-conquer/lecture/obhKq/randomized-selection-analysis}}
=Deterministic Selection=
=Deterministic Selection=
{{External3|https://www.coursera.org/learn/algorithms-divide-conquer/lecture/vtehr/deterministic-selection-algorithm-advanced-optional https://www.coursera.org/learn/algorithms-divide-conquer/lecture/2wmHr/deterministic-selection-analysis-i-advanced-optional https://www.coursera.org/learn/algorithms-divide-conquer/lecture/vOjvG/deterministic-selection-analysis-ii-advanced-optional}}
{{External3|
https://www.coursera.org/learn/algorithms-divide-conquer/lecture/vtehr/deterministic-selection-algorithm-advanced-optional
https://www.coursera.org/learn/algorithms-divide-conquer/lecture/2wmHr/deterministic-selection-analysis-i-advanced-optional https://www.coursera.org/learn/algorithms-divide-conquer/lecture/vOjvG/deterministic-selection-analysis-ii-advanced-optional}}
DSelect. Median of medians.
DSelect. Median of medians.

Revision as of 00:47, 28 September 2021

Internal

Overview

The ith order statistic of a set of n numbers is the ith smallest number in the set.

Finding the ith order statistic of a set of n distinct numbers (distinctness is for simplicity) is known as the selection problem. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element, by reducing the selection problem to the sorting problem. However, key comparison sorting cannot be done more efficiently than Ω(n lgn), and more specialized and faster algorithms exist for the selection problem. Fundamentally, selection is an easier problem than sorting.

The general selection problem can be resolved with a randomized divide-and-conquer algorithm with an expected running time of Θ(n). The algorithm is somewhat similar to the one used by randomized Quicksort. There is also a linear time algorithm for selection that does not use randomization; the idea is to use the pivot deterministically in a very careful way using a method called "median of medians".

TODO CLRS page 213.

Randomized Selection

RSelect.

Randomized Selection Analysis

https://www.coursera.org/learn/algorithms-divide-conquer/lecture/obhKq/randomized-selection-analysis

Deterministic Selection

https://www.coursera.org/learn/algorithms-divide-conquer/lecture/vtehr/deterministic-selection-algorithm-advanced-optional https://www.coursera.org/learn/algorithms-divide-conquer/lecture/2wmHr/deterministic-selection-analysis-i-advanced-optional https://www.coursera.org/learn/algorithms-divide-conquer/lecture/vOjvG/deterministic-selection-analysis-ii-advanced-optional

{{{2}}}
{{{3}}}

DSelect. Median of medians.