In this next series of videos, we'll get
some more practice applying the divide and
conquer algorithm and design paradigm to
various problems. This will also give us a
glimpse of the kinds of application
[inaudible] to which it's been
successfully applied. We're gonna start by
extending the merge sort algorithm to
solve a problem involving counting the
number of inversions of an array. Before
we tackle the specific problem of counting
the number of inversions in an array, let
me say a few words about the divide and
conquer paradigm in general. So again,
you've already seen the totally canonical
example of divide and conquer, namely
merge sort. So the following three
conceptual steps will be familiar to you.
The first step, no prizes for guessing is
you divide. The problem. Into smaller
sub-problems. Sometimes this division
happens only in your mind. It's really
more of a conceptual step than part of
your code. Sometimes you really do copy
over parts of the input into say new
arrays to pass on to your recursive calls.
The second step, again no prizes here, is
you conquer the sub-problems just using
recursion. So for example, in Merge Sort,
you conceptually divide the array into two
different pieces. And then you [inaudible]
with the conquer or sort to the first half
of the array. And you, you do the same
thing with the second half of the array.
Now, of course, it's not quite as easy as
just doing these two steps. Dividing the
problem, and then solving the sub problems
recursively. Usually, you have some extra
cleanup work after the recursive calls,
and to stitch together the solutions to
the sub problems into one for the big
problem, the problem that you actually
care about. Recall, for example, in Merge
Sort, after our recursive calls, the left
half of the array was sorted, the right
half of the array was sorted. But we still
had to stitch those together. Merge into a
sorted version of the entire array. So the
[inaudible] step is to combine. The
solutions to the subproblem into one
problem. Generally the largest amount of
ingenuity happens in the third step. How
do you actually quickly combine solutions
to subproblems into one to the original
problem? Sometimes you also get some
cleverness in the first step with
division. Sometimes it's as simple as just
spliting a ray in two. But there are cases
where the division step also has some
ingenuity. Now let's move on to the
specific problem of counting inversions
and see how to apply this divide and
conquer paradygm. So let begin by defining
the problem formally now. We're given as
input an array A with a length N. And you
can define the problem so that the array a
contains any ole distinct numbers. But,
let's just keep thing simple and assume
that it contains the numbers one through
n. The integers in that range in some
order. That captures the essence of the
problem. And the goal is to compute the
number of inversions of this array so
what's an inversion you may ask well an
inversion is just a pair of array
[inaudible] I and J with I smaller than J
so that earlier array entry the I entry is
bigger than the latter one the Jake one so
one thing that should be evident is that
if the array contains these numbers in
sorted order if the array is simply one
two three four all the way up to N then
the number of inversions is zero. The
converse you might also want to think
through if the array has any other
ordering of the numbers between one and N
other than the assorted one, then it's
going to have a non. Of zero number of
inversions. Let's look at another example.
So'spose we have an array of six entries.
So the numbers one thru six in the
following order. One, three, five followed
by two, four, six. So how many inversions
does this array have? So again what we
need to look for are pairs of array
entries so that the earlier or left entry
is bigger than the later or right entry.
So one example which we see right here
would five and two. Those are right next
to each other and out of order, the
earlier entry is bigger than the other
one. But there's others, there's three and
two for example Those are out of order.
And, five and four are also out of order.
And I'll leave it to you to check that
those are the only three pairs that are
out of order. So summarizing the
inversions in this array of length six are
3-2, 5-2, and 5-4. Corresponding to the
array entries, 2-4, 3-4, and 3-5.
Pictorially, we can think of it thusly, we
can first. Write down the numbers in
order, one up to six. And then we can
write down the numbers again but, ordered
in the way that their given in the input
array. So, one three five two four six.
And then we can connect the dots, meaning
we connect one to one. Reconnect two to
two, and so on. It turns out, and I'll
leave to for you to, to think this
through, that the number of crossing pairs
of line segments prescisely correspond to
the number of inversions. So we see that
there are one, two, three crossing line
segments. And these are exactly in
correspondence with the three inversions,
we found earlier. Five and two, three and
two, and five and four. Now, [inaudible]
wanna solve this problem you might ask.
Well there's few reasons that come up. One
would be to have a numerical similarity
measure that quantifies how close to
[inaudible] lists are to each other. So
for example, suppose I took you and a
friend, and I took, identified ten movies
that both of you had seen. And I asked
each of you to order, or to rank these
movies from your most favorite to your
least favorite. Now I can form an array,
and compute inversions. And it quantifies,
in some sense, how dissimilar your two
rankings are to each other. So in more
detail, in the first entry of this array,
I would put down the ranking that your
friend gave to your favorite movie. So if
you had your favorite movie, Star Wars or
whatever. And your friend only thought it
was the fifth best out of the ten, then I
would write down a five in the first entry
of this array. Generally, I would take
your second favorite movie. I would look
at how your friend ranked that. I would
put that in the second entry of the array
and so on, all the way up to the tenth
entry of the array, where I would put your
friend's ranking of your least favorite
movie. Now, if you have exactly identical
preferences, if you rank them exactly the
same way, the number of inversions of this
array would be zero. And in general, the
more inversions this array has, it
quantifies that your lists look more and
more different from each other. Now why
might you want to do this why might you
want to know whether two different people
ranked things in the similar way had
similar preferences well one reason might
be what's called collaborative filtering,
probably many of you have had the
experience of going to a website and if
you've made a few purchases through this
website it starts recommending further
purchases for you, so one way to solve
this problem under the hood, is to look at
your purchases look at what you seem to
like, find other people who have similar
preferences similar history look at things
they've bought that you haven't, and then
recommend. New products to you based on
what similar customers seemed to have
bought. So this problem captures some of
the essence of identifying which customers
or which people are similar based on data
about what they prefer. So just to make
sure we're all on the same page, let me
pause for a brief quiz. We've already
noticed that a given array will have zero
inversions, if and only if it's in sorted
order. If it only contains the numbers of
one through N in order. So, on the other
side, what is the largest number of
inversions an array could possibly have?
Let's say, just for an array of size six,
like the one in this example here. So the
answer to this question is the first one.
Fifteen. Or in general in an N. Element
array the largest number of inversions is
N. Choose two. Also known as N times N
minus one over two. Which, again, in the
case of a [inaudible] is going to evaluate
to fifteen. The reason is, the worst case
is when the array is in backwards order,
reverse [inaudible] order, and every
single pair of [inaudible] indices is
inverted. And so the number of indices IJ,
with I less than J is precisely
[inaudible] too. Let's now turn our
attention to the problem of computing the
number of inversions of an array as
quickly as possible. So one option that is
certainly available to us is the brute
force algorithm. And by brute force I just
mean we could set up a double four loop.
One which goes through I, one which goes
through J bigger than I, and we just check
each pair IJ individually with I less than
J whether that particular pair of array
entities AI and AJ is inverted and if it
is then we add it to our running count.
And then we return the final count at the
end of the double four loop. That's
certainly correct. The only problem is, as
we just observed, there's N [inaudible]
two or a quadratic number of potential
inversions so this algorithm's almost
going to run in time quadratic in the
array link. Now remember the mantra of any
good algorithm designer. Can we do better?
And the answer is yes. And the method
we'll be using, divide and conquer. The
way in which we'll divide will be
motivated directly by merge sort where we
recurs e separately on the left and the
right half's of the array. We're gonna do
the same thing here. To understand how
much progress we can make purely using
recursion let's classify the inversions of
array into one of three types. So suppose
we have an inversion of an array I, J, and
remember in an inversion you always have I
less than J. We're gonna call it a left
inversion. If both of the array indices
are at most N over two, where N is the
array length. We're gonna call it a right
inversion if they're both strictly greater
than N over two. And we're gonna call it a
split inversion if the smaller index is at
most N over two and the larger index is
bigger than N over two. We can discuss the
progress made by recursion in these terms.
When we recurse on the left-half of an
array, if we implement our algorithm
correctly, we'll successfully be able to
count all of the inversions located purely
in that first half. Those are precisely
the left inversions. Similarly, a second
recursive call on just the right half of
an array, the second half of an
[inaudible] array will successfully count
all of the right inversions. There remains
the questions of how to count the split
inversions. But we shouldn't be surprised
there's some residual work left over, even
after the recursive calls do their job.
That, of course, was the case at Merge
Short, where [inaudible] magically took
care of sorting the left half of the
array, sorting the right half of the
array. But there was still, after their
return, the matter of merging those two
sorted lists into one. And here again,
after the recursion is gonna be the matter
of cleaning up and counting the number of
split inversions. So for example if you go
back to the six element array we worked
through before, 135246, you'll notice that
there, in fact, all of the inversions are
split. So the recursive calls will both
come back counting zero inversions. And
all of the work for that example will be
done by the count split inversions
subroutine. So let's summarize where
things stand given underspecified high
level description of the algorithm as we
envision it. There is a base case. I'll go
ahead and write it down for completeness,
which is if we're given a one element
array, then there's certainly no inversion
so we can just immediately return the
answer zero. For any bigger array, we're
going to divde and conquer. So we'll count
the left inversions with a recursive call.
The right inversions with a recursive
call. And then we'll have some currently
unimplemented subroutine that counts the
split inversions. Since every inversion is
either left or right, or split, and can't
be any more than one of those three, then,
having done these three things, we can
simply return their sum. So that's our
high level attack on how we're gonna count
up the number of inversions. And of
course, we need to specify how we're gonna
count the number of split inversions. And
moreover, we lack that subroutine to run
quickly. An analogy to emerge short,
where, outside the recursive calls, we did
merely linear work. Outs-, in the merge
subroutine. Here, we'd like to do only
linear work in counting up the number of
split inversions. If we succeed in this
goal, if we produce a correct and linear
time of limitation to count up the number
of split incursions, then this entire
recursive algorithm will run in big O. Of
N. Log in time. The reason the overall out
rhythm will run in O. Of N. Log in time is
exactly the same reason that merge short
ran in N. Log in time. There's two
recursive calls. Each on a problem of
one-half the size. And outside of the
recursive calls we would be doing linear
work. So you could copy down exactly the
same recursion tree argument we used for
merge short. It would apply equally well
here. Alternatively, very soon we will
cover the master method, and as one very
special case it will prove that this
algorithm, if we can implement it thusly,
will run in O. Of N. Log in time. Now one
thing to realize, is this is a fairly
ambitious goal, to count up the number of
split inversions in linear time. It's not
that there can't be too many split
inversions. There can actually be a lot of
them. If you have an array where the first
half of the array contains the numbers N
over two plus one, up to N. Whereas the
second part of the array contains the
numbers one up to N over two, that has a
quadratic number of inversions, all of
which are split. So, what we're attempting
to do here is count up a quadratic number
of things using only linear time. Can it
really be done? Yes is can, as we'll see
in the next video.