Previous videos covered an outstanding
algorithm for the selection problem, the
problem of computing the Ith statistic of
a given array. That algorithm which we
called the R select algorithm was
excellent in two senses. First its super
practical, runs blazingly fast in
practice. But also it enjoys a satisfying
theoretical guarantee. For every input
array of length N at the expected running
time of R select is big O of N, where the
expectation is over the random choices of
the pivots that R select makes during
execution, now in this optional video
I'm going to teach you yet
another algorithm for the selection
problem. Well why bother given that our
select is so good? Well frankly, I just
can't help myself. The ideas of this
algorithm are just too cool not to tell
you about, at least in optional video like
this one. The selection algorithm
, we cover here is deterministic.
That is, it uses no randomization
whatsoever. And it's still gonna run in
linear time, big O of N time. But now, in
the worst case for every single input
array. Thus, the same way Merge Short gets
the same asymptotic running time, big O
of N log N, as quick sorts gets on
average. This deterministic algorithm will
get the same running time O of N, as the R
select algorithm does on average. That
said, the algorithm we're gonna cover
here, well, it's not slow. It's not as
fast as R select in practice, both because
the hidden constants in it are larger. And
also because it doesn't' operate in place.
For those of you who are feeling keen, you
might wanna try coding up both the
randomized and the deterministic selection
algorithms, and make your own measurements
about how much better the randomized one
seems to be. But if you have an
appreciation for Boolean algorithms, I
think you'll enjoy these lectures
nonetheless. So let me remind of the
problem. This is the i-th order
statistic problem. So we're given an
array, it has N distinct entries. Again,
the distinctness is for simplicity. And
you're given a number I between one and N.
You're responsible for finding the
i-th smallest number, which we call
the i-th order statistic. For
example, if I is something like N over
two, then we're looking for the median. So
let's briefly review the randomized
selection algorithm. We can think of the
deterministic algorithm covered here as a
modification of the randomized algorithm,
the R select algorithm. So when that
algorithm is passed in array with length
N, and when you're looking for the
i-th order statistic, as usual,
there's a trivial base case. But when
you're not in the base case, just like in
Quick Sort, what you do is you're gonna
partition the array around pivot element
P. Now, how are you gonna choose P? Well,
just like Quick Sort, in the randomized
algorithm, you choose it uniformly at
random. So each of the N elements of the
input array are equally likely to be
chosen. As the pivot. So, call that pivot
p. Now, do the partitioning. Remember
partitioning puts all of the elements less
than the pivot to the left of the pivot.
We call that the first part of the
partitioned array. Anything big, bigger
than the pivot gets moved to the right of
the pivot. We call that the second part of
the array. And let j denote the position
of the pivot in this partitioned array.
Equivalently, let j be what order
statistic that the pivot winds up
happening to be. Right? So, we happen to
choose the minimum element then J's gonna
be equal to one. If we happen to choose
the maximum element, J's gonna be equal to
n. And so on. So, there's always the lucky
case, chance one in N, that we happen to
choose the Ith order statistic as our
pivot. So, we're going to find that out
when we notice that J equals I. In that
super lucky case, we just return the pivot
and we're done. That's what we're looking
for in the first place. Of course, that's
so rare it's not worth worrying about, so
really the two main cases depend on
whether the pivot that we randomly choose
is bigger than what we are looking for or
if it's less than what we are looking for.
So, if it's bigger than what we are
looking for, that means J is bigger than
I, we're looking for the Ith smallest, we
randomly chose the J'th smallest. Then
remember we know that the Ith smallest
element has to lie to the left of the
pivot. Good element in that first part of
the partition array. So we recurs there.
It's an array that has J-1 elements in it,
everything less than the pivot. And we're
still looking for the Ith smallest among
them. In the other case, this was the case
covered in a quiz a couple videos back, if
we guess a pivot element that is less than
what we're looking for, well then we
should discard everything less than the
pivot and the pivot itself. So we should
recurs on the second part of A, stuff
bigger than the pivot. We know that's
where what we're looking for lies. And
having thrown away J elements, the
smallest ones at that. We're rehearsing on
a ray of [inaudible] and minus J, I'm
looking for the [inaudible] smallest
element in that second part. So, that was
the randomized selection algorithm, and
you'll recall the intuition for why this
works is random pivot should usually give
pretty good splits. So the way the
analysis went is we should. Each
iteration, each recursive call, with 50
percent probability, we get a 25/75 split
or better. Therefore, on average, every
two recursive calls, we are pretty
aggressively shrinking the size of the
recursive call. And for that reason, we
should get, something like a linear time
bound. We do almost as well as if we
picked the median in every single call,
just because random pivots are a good
enough proxy of best case pivots, of. The
median. So now the big question is:
suppose we weren't permitted to make use
of randomizations. Suppose this
choose-a-random-pivot trick was not in our
tool box. What could we do? How are we
going to deterministically choose a good
pivot? Let's just remember quickly what it
means to be a good pivot. A good pivot is
one that gives us a balanced split, after
we do the partitioning of the array. That
is, we want as close to a 50/50 split
between the first and the second parts of
the partitioned array as possible. Now,
what pivot would give us the perfect 50/50
split? Well, in fact, that would be the
median. Well, that seems like a totally
ridiculous observation, because we
canonically, are trying to find the
median. So previously we were able to be
lazy, and we just picked a random pivot,
and used that as a pretty good proxy for
the best case pivot. But now, we have to
have some subroutine that
deterministically finds us a pretty good
approximation of the median. And the big
idea in this linear time selection
algorithm, is to use what's called the
median of medians as a proxy for the true
meaning of the input array. So when I say
median of medians, you're not supposed to
know what I'm talking about. You're just
supposed to be intrigued. Now, let me
explain a little bit further. Here's the
plan, we're gonna have our new
implementation of chose pivot and it's
gonna be deterministic. You will see no
randomization on this slide, I promise. So
the high-level strategy is gonna be we're
gonna think about the elements of this
array like sports teams, and we're gonna
run a tournament, a 2-round. Knockout
tournament, and the winner of this
tournament is going to be who we return as
the proposed pivot element. Then we'll
have to prove that this is a pretty good
pivot element. So there's gonna be two
rounds in this tournament. Each element,
each team is gonna first participate in a
world group, if you will. So they'll be,
small groups of five teams each, five
elements each. And to win your first
round, you have to be the middle element
out of those five. So that'll give us N
over five first round winners. And then
the winner of that second round is going
to the med-, be the median of those N over
five winners from the first round. Here
are the details. The first step isn't
really something you actually do in the
program, it's just conceptually. So
logically, we're going to take this array
capital A, which has N elements, and we're
gonna think of it as comprising N over
five groups with five elements each. So if
N is not a multiple of five, obviously,
there'll be one extra group that has size
between one and four. Now for each of
these groups of five, we're going to
compute the median, so the middle element
of those five. Now for five elements, we
may as well just invoke a reduction to
sorting; we're just gonna sort each group
separately, and then use the middle
element, which is the median. It doesn't
really how you do the sorting. Because
after all, there's only five elements. But
you know, let's use [inaudible] sort, what
the heck. Now what we're going to do is
we're going to take our first round
winners and we're gonna copy them over
into their own private array. Now this
next step is the one that's going to seem
dangerously like cheating, dangerously
like I'm doing something circular and not
actually defining a proper algorithm, so c
you'll notice has linked over n over five.
We started with an array of link n. This
is a smaller input. So let's recursively
compute the median of this array capital
c. That is the second round of our
tournament amongst the n over five
first-round winners, the n over five
middle elements of the sorted groups. We
recursively compute the median, that's our
final winner, and that's what we return as
the pivot element from this subroutine.
Now I realize it's very hard to keep track
of both what's happening internal to this
juice pivot subroutine and what's
happening in the calling function of our
deterministic selection algorithm. So let
me put them both together and show them to
you, cleaned up, on a single slide. So,
here is the proposed deterministic,
selection algorithm. So, this algorithm
uses no randomization. Previously, the
only randomization was in choosing the
pivot. Now we have a deterministic
subroutine for choosing the pivot, and so
there's no randomization at all. I've
taken the liberty of in-lining true's
pivot subroutine. So that is exactly what
lines one, two, and three are. I haven't
written down the base case just to save
space I'm sure you can remember it, so if
you're not in the base case. What did we
do before? The first thing we do is choose
a random pivot. What do we do now? Well,
we have steps one through three. We do
something much more clever to choose a
pivot. And this is exactly what we said on
the last slide. We break the array into
groups of five. We sort each group, for
example, using merge sort. We copy over
the middle element of each of the n over
five groups into their own array capital
c. And, then, we recursively compute the
median of c. So, when we recurs on select
that we pass the input c. C has n over
five elements so that's the new link.
That's a smaller link than what we start
with so it's a legitimate recursive call
refining the median of n over five
element. So, that's gonna be the n over
tenth order statistic. As usual. Well to
keep things clear I'm ignoring stuff like
fractions, in your real implementation
you'd just round it up or down. As
appropriate. So steps one through three
are the new [inaudible] step routine that
replaces the randomized selection that we
had before. Steps four through seven are
exactly the same as before. We've changed
nothing. All we have done is ripped out
that one line where we chose the pivot
randomly and pasted in these lines one
through three. That is the only change to
the randomized selection algorithm. So,
the next quiz is a standard check that you
understand this algorithm, at least, not
necessarily why it?s fast; but, at least,
just how it actually works. And I only ask
you to identify how many recursive calls
there are, each time. So, for example in
[inaudible] there's two recursive calls,
in quick-sort there's two recursive calls,
in r-select there's one recursive call.
How many recursive calls do you have each
time, outside of the base case in the
d-select algorithm? All right, so the
correct answer is two. There are two
recursive calls in deselect, and maybe the
easiest way to answer this question is not
to think too hard about it and literally
just inspect the code and count, right
namely there's one recursive call in line
three, and there's one recursive call in
either six or seven, so quite literally,
you know there's seven lines of code, and
two of the ones that get executed have a
recursive call so the answer is two. Now
what's confusing is that in the random, a
couple things, first in the randomized
selection algorithm, we only have one
recursive call. We have the recursive
call. In line six or seven, we didn't have
this in line three. That one in line three
is new compared to the randomized
procedure. So we're kind of used to
thinking of one recursive call using the
divide and conquer approach to selection,
here we have two. Moreover. Conceptually.
The roll of these two recursive calls are
different. So the one in line six or seven
is the one we're used to. That's after
you've done the partitioning so you have a
smaller sub-problem and then you just
recursively find the residual or statistic
in the residual array. That's sort of the
standard divide and conquer approach.
What's sort all crazy. Is this second use
of a recursive call which is part of
identifying a good pivot element for this
outer recursive call and this is so
counter-intuitive, many students in my
experience don't even think that this
algorithm will hold, sort of, they sort of
expect it to go into an infinite loop. But
again, that sort of over thinking it. So
let's just compare this to an algorithm
like merge sort. What does merge sort do?
Well it does two recursive calls and it
does some other stuff. Okay. It does
linear work. That's what it does to merge.
And then there are two recursive calls on
smaller sub problems, right? No issue. We
definitely feel confident that merge
[inaudible] is gonna terminate because the
sub problems keep getting smaller. What
does deselect do, if you squint? So don't
think about the details just [inaudible]
high level. What is the work done in
deselect? Well. There are two recursive
calls, there's [inaudible] one's in line
three, one's in line six or seven, but
there's two recursive calls on sm, smaller
sub problem sizes. And there's some other
stuff. There's some stuff in steps one and
two and four, but whatever. Those are
recursive calls. It does some work. Two
recurs have caused the smaller
sub-problems, TI's got to terminate. We
don't know what the run time is, but it's
got to terminate, okay? So if you're
worried about this terminating, forget
about the fact that the two recurs of
cause have different semantics and just
remember, if ever, you only recurs on
smaller sub-problems, you're definitely
going to terminate. Now, of course who
knows what the running time is? I owe you
an argument on why it would be anything
reasonable, that's going to come later. In
fact what I'm gonna prove to you is not
only does this selection algorithm
terminate, run in finite time, it actually
runs in linear time. No matter what the
input array is. So where as with R select,
we could only discuss its expected running
time being linear. We showed that with
disastrously bad choices for pivots, R
selects can actually take quadratic time.
Under no circumstances will deselect ever
take, ever take quadratic time. So for
every input array it's big O of N time.
There's no randomization because we don't
randomly do anything in choose pivot, so
there's no need to talk about average
running time; just the worst case running
time over all inputs is O of N. That said,
I want to reiterate the warning I gave you
at the very beginning of this video which
is, if you actually need to implement a
selection algorithm, you know, this one
wouldn't be a disaster. But it is not the
method of choice, so I don't want you to
be misled. As I said there are two reasons
for this. The first is that the constants
hidden in the begon notation are larger
for V select than for R select. That will
be somewhat evident from the analyses that
we give for the two algorithms. The second
reason is, recall we made a big deal about
how partitioning works in place and
therefore quicksort and r select also work
in place, that is, with no real additional
memory storage. But in this deselect
algorithm we do need this extra array c to
copy over the middle elements, the first
round winners. And so the extra memory, as
usual, slows down the practical
performance. One final comment. So for
many of the algorithms that we cover, I
hope I explain them clearly enough that
their elegance shines through and that for
many of them you feel like you could have
up with it yourself, if only you'd been in
the right place at the right time. I think
that's a great way to feel and a great way
to appreciate some of these very cool
algorithms. That said, linear time
selection, I don't blame you if it, if you
feel like you never might have come up
with this algorithm. I think that's a
totally reasonable way to feel after you
see this code. If it makes you feel
better, let me tell you about who came up
with this algorithm. It's quite old at
this point, about 40 years, from 1973. And
the authors, there are five of them and at
the time this was very unusual. So, Manuel
Blum. Bob Floyd. Vaughn Pratt. Ron Rivest.
And Bob Targen. And this is a pretty heavy
weight line up, so as we've discussed in
the past, the highest award in computer
science is the ACM Turing award given once
each year. And I like to ask my algorithms
classes how many of these authors do they
think, have been awarded a Turing award.
I've asked him many times. The favorite
answer anyone's ever given me has been.
Six, which I think is in spirit should be
correct. Strictly speaking the answer is
four. So, the only one of these five
authors that doesn't have a Touring award
is Von Pratt, although he's done
remarkable things spanning the gambit from
co-founding Sun Systems to having very
famous theorems about, for example,
testing primality. But the other four have
all been awarded the Touring award at some
point. So in chronological order, so the
late Bob Floyd who was a professor here at
Stanford. Was awarded the 1978 [inaudible]
award, both for contributions to
algorithms but also to program languages
and compilers. So Bob Targen who, as we
speak, is here as a visitor at Stanford
and has spent his Ph. D here and has been
here as a faculty at times, was awarded it
for contributions to graph algorithms and
data structures. We'll talk some more
about some of his other contributions in
future courses. Manuel Blum was awarded
the Turing award in'95 largely for
contributions in cryptography, and many of
you probably know Ron Rivest as the R in
the RSA cryptosystem. So he, won the,
Turing award along with Shamir and Adleman
back in'02. So in summary, if this
algorithm seems like one that might have
alluded you even on your most creative
days, I wouldn't feel bad about it. This
is a, this is a quite clever algorithm. So
let's now turn to the analysis and explain
why it runs in linear time in the worst