Randomized Algorithms - Finding median in linear time

Presentation and probabilistic analysis of a randomized algorithm for finding the median element of an array of integers in linear time, thus avoiding a full sort of the array.