0:35

the median and element distinctness. I just talked about the scheduling problem,

reduces the topological sort. we saw that in the shortest paths lecture. Also, the

arbitrage problem of is, involves building a, a, a digraph for currency exchange. we

reduce that to shortest paths. and there's several other examples. So, it's an

important and useful technique. so that just the general mentality is, if I know

how to solve Y, I have a new problem. can I use that to solve X? and every

programmer does that and saying, well, I've got some code that solves Y or I've

got a library function that does Y. Can I use that to solve X? That's reduction. So,

our first example is convex hull problem that we looked at briefly back in the

sorting lecture. And, and that's where your given endpoints in the plane and what

you want to do is, I identify the points on the periphery, these, that's called

extreme points on the convex hull. you can imagine a, a bunch of points on a big

range and a rancher wants to use the cheapest amount of fence to surround them

all. And so it's a minimum parameter way to draw a line that surrounds all the

points, it's a convex hull. and there's many other ways to define it. That doesn't

seem to be all that closely related to sorting but it's actually true that convex

hull reduces the sorting. that is if you can sort, you can compute the convex hull.

And that's an algorithm known as the Graham scan algorithm that we'll look at

in the next slide. the cost of a convex hull is the cost of the sort and log N

plus the cost of the reduction. And that Graham scan algorithm just uses linear

time. So, with sorting we get an N log N algorithm for convex hull, which is a nice

algorithm design technique. And this is a diagram of the, that shows the Graham scan

algorithm we which we won't go through in detail but it's pretty intuitive. what we

do is we pick a point one over in the corner and maybe the smallest Y coordinate

point. and then, sort the points by polar angle swept out by that coordinate. so, if

you think of a, of a line sweeping through and just picking out the points by polar

angles centered at that point, then we get the points in order along this polygon.

And because we're doing it by polar angle the lines don't intersect. It's a simple

polygon which with no intersecting lines. And then, the Graham scan algorithm is

just to proceed along, over here, it proceeds along that polygon. but if you

ever come to a point where you are going to make a right turn or clockwise turn you

throw out the points that would have caused that. So, in this case, this point

will cause us to make a right turn so we throw it out. And now, our most recent

points are these three. And again, that's a right point, so we throw that one out

and it puts us in this position here and so, and the idea is that any point that

would cause a right-hand turn is not going to be on the convex hull. It's going to

kind of a, we kind of have a proof that the points inside just buys into the fact

that it would make us do a right turn. So, we throw this one out and that leaves that

and then we go here. And that would be a right turn on the, on our path. So throw

that one out, and we're here. Another one and continuing in this way. when we

finally get back to the beginning we've computed the points on the convex hull.

So, the cost of the algorithm is the cost of the sort which is N log N. But the cost

of the scan is only linear. Every point only gets considered once. that's an

excellent example of a reduction to get a new algorithm. If you didn't have the fast

sort this wouldn't be so effective. here's another example of a reduction we

implemented and looked at short est path for digraphs. what about shortest paths on

undirected graphs? It still makes sense. That's why I have a weighted undirected

graph with non-negative weights and I'm going to find the shortest path from a

given vortex, source vortex, S2 or a given target vortex T, and if it's the lowest

weight path from S to T. so how are we gonna solve that one? We have shortest

path that works for digraphs. Well, if we just replace each undirected edge by two

directed edges, then the shortest path algorithm for digraphs works. in fact,

with our graph representation it's just running that algorithm cuz our undirected

graphs are represented with the edges going in both directions so they're

actually represented as digraphs. and again, what's the cost? the cost this time

is the cost of pre-processing to just take the graph in its undirected form and

convert it to directed form and then the cost of shortest pass of the digraph is E

log V. So that gives us an algorithm for shortest path in undirected graphs. Notice

that it doesn't work if there's negative weights in the undirected graph, because

the reduction creates a negative cycle. it is possible to find shortest paths in

these graphs but you need a, a much more sophisticated algorithm to do it. so just

continuing in this way we've considered quite a few problems that involved

reductions. so, I just talked about finding median and element distinctness in

convex hull reducing to sorting. and there were a bunch of other problems that we

considered as exercises when we talked about applications to applications of

sorting. So, application of sorting really means problem reduces to sorting. so sure

as processing time scheduling and, and, and lots of other problems that are

reduced to sorting. and in the graph world we looked at some pretty complicated

problems. Arbitrage we looked at a parallel, parallel scheduling or CPM

method and I just talked about shortest paths and undirected graphs and those all