0:03

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.