Question

Who are the five scientists who came up with the linear time selection algorithm? How many of them are still alive? What is the title of their original paper? What basis did they have for thinking that a linear time algorithm existed for this problem?

Answer 1

The five scientists are

Names Worked at Alive/Died   

1.Manuel Blum - professor at U.C. Berkeley - Alive   

2.Robert W. Floyd -professor at Stanford    -Died(September 25, 2001)

3.Vaughan Ronald Pratt -professor at Stanford -Alive

4.Ronald Linn Rivest -Webster Professor of Electrical

Engineering and CS at MIT    -Alive

5.Robert Endre Tarjan - professor at Princeton     - Alive

4 among these scientists are alive

Robert W. Floyd Died Remaining scientists are Alive

Original paper:

ICS 161, Winter 1996 : Design and Analysis of Algorithms

Basis for this problem:

Review that quick select which picks an random "pivot" x, it partitions the list into elements less than and greater than x, and calls itself recursively in one of the two sub-lists. The significantly speedier determination strategy we plot accomplishes something comparative, yet picks the pivot in a complicated manner, by calling itself recursively in an random. so the deterministic calculation will utilize a similar thought of picking x by playing out a recursive call.

On the off chance that we could do so rapidly, one good choice would simply be to let x be the median of the values. At that point each recursive call would just be on a subset of a Half of the values. Obviously in the event that we realized how to locate the middle, we'd be done, so finding the middle is too great to even think about hoping for. Rather allows simply attempt to get something near the middle (say inside n/4 places of it). At that point each recursive call would be on a bigger part of the info (3n/4) however this still may be adequate.