Today we're going to talk about
reductions. this is something that we've
done several times throughout the course,
but we're going to want to take a little
bit more formal look at it, because it
plays a critical role in some of the
advance, advanced topics that we're going
to want to consider next. Just a quick
overview of the next few lectures. These
are advanced topics related to algorithms
and you can take more advance courses that
go into all these things in depth. But
it's important to talk about them in
context of the algorithm so that we seem
to put everything into, into perspective
So what we're going to talk about in this
lecture is called reduction and it's a
technique that we use t take the good
algorithms that we know and use them
effectively to build more complicated
algorithms. And as I said, we've done that
before but it brings up some interesting
ideas. that are bigger than any particular
algorithm. And one idea that we've talked
about is the idea of a problem-solving
model. We saw that we could use shortest
paths and max flow to solve problems that
didn't seem to be related at all. and
there's a particularly important
problem-solving model called linear
programming that we'll talk about in the
next lecture. but then there's a limit,
and that brings us to the topic of
intractability that we'll talk about in
the last lecture. So we're shifting gears
from individual problems to thinking about
problem-solving models that are more
general than a particular individual
problem. And also, as part of this, we're
moving into problems that are much more
difficult to solve. And not just linear
and quadratic fast algorithms, but a just
a different scale. And we'll talk about
that in the next couple of lectures. And
then we're not going to really be talking
that much about code for awhile. It's more
about the conceptual framework and where
the problems that you really want to work
on fit into the big picture. So the, our
goals are we've looked at some terrific,
fantastic, very useful classical
algorithms. But they fit into a larger
context. we're going to encounter new
problems. you want to have all those
algorithms in the tool box, but you also
under. Want to understand where they fit
in to the big picture. there's some very
interesting, important and essential ideas
that have been developed at in great depth
over the past several decades. and it's
important for every practitioner to, have
a good feeling for, for those ideas and,
and what they imply. and really, by
thinking about these big ideas, in
addition to particular algorithms for
particular problems, most people find that
they're inspired to learn much more about
algorithms. So by way of introduction
let's talk about what a reduction is. So
this is just a big bird's eye view. The
idea is that what we would really like to
do is if we, if we have a new problem that
we have solve, we'd like to be able to
classify the problem according to the cost
that it's going to take to solve it.
what's, what's an order of growth of a, of
an algorithm, a good algorithm or any
algorithm to solve the problem. And we've
already touched on this a little bit when
we talked about sorting algorithms. not
only did we have a, a good algorithm for
solving sorting several good algorithms
but we also developed a lower bound that
said that no algorithm can do better. And
so we can think of the sorting problem as
classified as being order-of-growth,
linearithmic or N log N. And then we saw
plenty of linear time algorithms that we
just examine all the data and we can get
it solved. And we like to have more things
like this other algorithms that we need
quadratic time to solve and so forth. So
we're going to think about how difficult
are problems to solve, that's the first
idea. Now there's really frustrating news
on this front that we'll be talking about
over the next couple of lectures. And the
frustrating news is there are a large
number of practical problems that we'd
like to solve that we don't really know
how hard they are to solve. And that's a
profound idea that we'll get to soon. so,
but what we want to talk about in this
lecture is one of the most important tools
that we use to try to classify problems.
and it's actually been very successful, in
lots of instances. And so if we know that
we could solve some problem efficiently we
want to use that knowledge to figure out
what else we could or could not solve
efficiently. And that's what reduction is
all about. It's just a single tool and
maybe kind of gets to this Archimedes
quote, give me a lever long and a fulcrum
on which to place it and I will move the
world. that's what reduction does for us.
So here's the basic idea. we say that a
problem X reduces to a problem Y. If you
can use a problem that solves Y to help
solve X. so, what does that mean? This
schematic diagram gives an idea of what we
are talking about. so, in the middle, we,
we assume that we have a, in the middle
box there, labeled in blue. And so, we
have an algorithm for solving problem y
in, it's not really relevant what that,
algorithm is? It just knows that if you
have any instance of problem y you can
solve it. And the idea behind reduction is
that we take an instance of problem X and
we transform it into an instance of
problem Y. Then use the algorithm for Y to
solve that instance of Y and then
transform the solution back to the
solution to be the instance of problem X.
So we take that transformation into an
instance of problem y. The transformation,
the solution back to a solution 2x. Then
that whole thing enclosed in the box on
the dotted line is an algorithm for
problem X. And what's the cost? The cost
of solving problem X is the cost of
solving Y. Plus the cost of reduction.
It's like pre-processing and
post-processing for, problem Y. Then we
see a number of calls to Y, in a
reduction. And the pre-processing and
post-processing might be, expensive.
Again, we've seen some specific examples
of this, and we'll go over it, in a
minute. so here's a really simple example.
finding the median, reduces to sorting. So
in this case problem Y is sorting and so
we assume that we have a sorting
algorithm. If you need to find a median,
then we take the items that's the instance
of X in this case there's no
transformation just sort and then once
they're sorted, you take that sorted
solution and just pick the middle, middle
item and return it so the transformation
of solution is also easy. so the cost of.
Solving, finding the median is the cost of
sorting which is N log N plus the cost of
the reduction which is just constant time.
If you can sort you can find the median.
So finding the median reduces to sorting
so here's a, a second, simple example.
suppose problem X is the element
distinctness problem and so that one is,
you have a bunch of elements. And you want
to know if they're all different. an easy
way to solve that, that we looked at back
in the coding lecture, is, again, just
sort. We assume that we have a sorting
algorithm. And then we take that instance
of, the element, the distinctness problem,
and just all the elements, and sort them.
And then after you sort'em, then you can
just go through, and, any items that are
equal are going to be adjacent to each
other. So, simply make a path through, in
this post processing phrase, and check,
adjacent pairs for equality, 'cause
anything equal's going to be right next to
one other. And that gives a solution to
the element distinctness problem. So
again, element distinctness reduces to
sorting, because you use sorting to solve
it. And in this case the cost of solving
element distinctness is the cost of
sorting and log N, plus cost of reduction,
this time you have to make a path through
it. So this means that we can solve
element distinctness in time proportional
to N log N. it could be that you could
find, a algorithm that doesn't use sorting
to solve element distinctness. But that
might be a bit of a challenge. by
reduction. maybe the hard work is done by
the sorting. and we get an algorithm for
this other problem. that's the basic idea.
As long as these cluster reductions not
too much, that's the basic idea, of being
able to use red uctions.
To design new algorithms.