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

Â