[ Pobierz całość w formacie PDF ]
Welcome back to algorithms. Today, we'regoing to talk about the union findproblem. A set of algorithms for solvingthe so-called dynamic connectivityproblem. We'll look at two classicalgorithms. Quick Find and Quick Union,and some applications and improvements ofthose algorithms. The subtext of today'slecture really is to go through the stepsthat we'll follow over and over again todevelop a useful algorithm. The first stepis to model the problem. Try tounderstand, basically, what are the mainelements of the problem that need to besolved. Then we'll find some algorithm tosolve the problem. In many cases, thefirst algorithm we come up with would befast enough and maybe it fits in memoryand, we'll go ahead and use it, and be offand running. But in many other cases maybeit's not fast enough, or there's notenough memory. So, what we do is try tofigure out why, find a way to addresswhatever's causing that problem, find anew algorithm and iterate until we'resatisfied. This is the scientific approachto designing and analyzing algorithms,where we build mathematical models to tryand understand what's going on, and thenwe do experiments to validate those modelsand help us improve things. So, firstwe'll talk about the dynamic connectivityproblem, the model of the problem forunion find. So, here's the idea. They'regoing to have a set of N objects. Doesn'treally matter what they are. We're goingto use the numbers, zero through N tomodel our objects. And then, we have theidea of a connection between two objects.And, we'll, postulate that there's goingto be a command that says, connect twoobjects. Given two objects, provide aconnection between them. And then key partof the problem is find query or theconnected query, which just asks, is therea path connecting the two objects. So forexample, in this set of ten objects, weperformed already, a bunch of unioncommands, connecting four and three, threeand eight, six and five, nine and four,two and one. And now we might have aconnected query that says, is zero connected to seven? Well, in this case, there isno connection, so we say no. But if we askis eight connected to nine? We are goingto say yes, even no we don't have a directconnection between eight and nine. Thereis a path from eight to three to four tonine. So, that's our problem, to be ableto officially support these two commandsfor given set of objects. Now, let's saywe add a union five, zero. So, thatcreates a connection between five andzero. Seven and two creates a connectionbetween seven and two. And six and one,between six and one. So, now if we ask ourzero connected to seven, well one and zerowe can do that too. And that's a redundantconnection. And now, if we ask is zeroconnected to seven we're going to answeryes. So that's our problem, intermixunion, commands and connected queries andwe need to be able to officially supportthose commands for a large number ofobjects. So, here's a much bigger example.And you can see that we're going to needefficient algorithms for this. First ofall, you can see we're going to need acomputer for this. It would take quite,quite some time for a human to figure outwhether there's a connection. In this casethere is a connection. Now, the algorithmsthat we're looking at today are not goingto actually give the path connecting thetwo objects. It's just going to be able toanswer the question, is there a path? Inpart two of the course, we'll consideralgorithms that explicitly find paths.They're not as efficient as union findbecause they have more work to do. Now,applications of these, these algorithmsinvolve objects of all types. These areused for digital photos, where the objectsare pixels they're used for networks,where the objects are computers, socialnetworks, where it's people, or computerchips, where it's circuit elements orabstract things like variable names in aprogram, or elements in a mathematicalset, or physical things like metallicsites in a composite system. So, alldifferent types of objects for, but forprogramming we're going to associate eachobject with a name and we'll just name theobjects with a number, integers from zeroto N-1. That's a very convenient initialstarting point for our programs because wecan use integers as an index into an arraythen, and then quickly access informationrelevant to each object. And it also justsupresses a lot of details that are notrelevant to union find. In fact, to makethis mapping from an object name to theinteger zero through N - one is to findapplication of a symbol table or asearching algorithm, which is one of thethings that we'll be studying later inthis course algorithms and data structuresfor solving that problem. Now, theconnections, well, we need, a few abstractproperties that these connections have tosatisfy. And they're all quite natural andintuitive. So we assume that is connectedto is an equivalence relation. That is,every object's connected to itself, it'ssymmetric. If P's connected to Q, then Q'sconnected to P, and it's transitive. IfP's connected to Q, and Q's connected toR, then P's connected to R. Now theseproperties are very intuitive. But it'sworthwhile to state them explicitly andmake sure that our algorithms maintainthem. When we have an equivalence relationa set of objects and connections divideinto subsets called connected components.A connected component is a maximal set ofobjects that's mutually connected. Forexample in this small example here,there's three connected components. Oneconsisting of just object zero, second oneobjects one, four and five. And third onethe other four objects. And thesecomponents have the property that if anytwo objects in them are connected andthere is no object outside that isconnected to those objects, that'sconnected components. Our algorithms willgain efficiency by maintaining connectedcomponents and using that knowledge toefficiently answer the query that's, thatthey're presented with. Okay, so toimplement the operations, we have to findquery and the union command. And so we'regoing to mai ntain the connectedcomponents. The find is going to have tocheck if two objects are in the samecomponent and the union command is goingto have to replace components containingtwo objects with their union. So, forexample, if we have these components, andwe get the command to union connect, twoand five. Essentially, we need to mergethe connected components containing theone containing two or the one containingfive to get a big connected components andnow we have only two connected components.All of that leads up to, in a programmingworld to specifying, a data type which issimply specification of the methods thatwe are want to going to implement in orderto solve this problem. So you know,typical Java model, what we will do iscreate a class called UF that contains twomethods, one to implement union, the otherone to implement connected, which returnsa boolean. The constructor, takes SR unit,the number of objects, so that it canbuild data structure based on the numberof objects. So, and we have to, bear inmind, as we're building our logarithms,that both the number of objects can behuge, but also, the number of operations.We can have a, a very large number, ofunion and connected, operations and ouralgorithms are going to have to beefficient, under those conditions. One ofthe practices that will follow often inthis course is to check our API designbefore getting too far into dealing withthe problem, by building a client that isgoing to use the data type that wedevelop. So, for this example, we've got aclient that, Will read information fromstandard input. First, an integer which isthe number of objects that are going to beprocessed. And then a series of pairs ofobject names. And what the client does isit, it'll, first it'll read the integerfrom standard input, and create a, a UFobject. And then as long as standard inputis not empty, it's going to read twointegers from the input. And if they'renot connected, then it'll connect them andprint them out. If they are connectedit'll ignore. So, that's our test clientand that's a fine test client to make surethat any implementation does what weexpect that it will. So, that's the setup.We've described the operations we want toimplement all the way down to code and wehave client code that we're going to haveto be able to service with our [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl jajeczko.pev.pl
Welcome back to algorithms. Today, we'regoing to talk about the union findproblem. A set of algorithms for solvingthe so-called dynamic connectivityproblem. We'll look at two classicalgorithms. Quick Find and Quick Union,and some applications and improvements ofthose algorithms. The subtext of today'slecture really is to go through the stepsthat we'll follow over and over again todevelop a useful algorithm. The first stepis to model the problem. Try tounderstand, basically, what are the mainelements of the problem that need to besolved. Then we'll find some algorithm tosolve the problem. In many cases, thefirst algorithm we come up with would befast enough and maybe it fits in memoryand, we'll go ahead and use it, and be offand running. But in many other cases maybeit's not fast enough, or there's notenough memory. So, what we do is try tofigure out why, find a way to addresswhatever's causing that problem, find anew algorithm and iterate until we'resatisfied. This is the scientific approachto designing and analyzing algorithms,where we build mathematical models to tryand understand what's going on, and thenwe do experiments to validate those modelsand help us improve things. So, firstwe'll talk about the dynamic connectivityproblem, the model of the problem forunion find. So, here's the idea. They'regoing to have a set of N objects. Doesn'treally matter what they are. We're goingto use the numbers, zero through N tomodel our objects. And then, we have theidea of a connection between two objects.And, we'll, postulate that there's goingto be a command that says, connect twoobjects. Given two objects, provide aconnection between them. And then key partof the problem is find query or theconnected query, which just asks, is therea path connecting the two objects. So forexample, in this set of ten objects, weperformed already, a bunch of unioncommands, connecting four and three, threeand eight, six and five, nine and four,two and one. And now we might have aconnected query that says, is zero connected to seven? Well, in this case, there isno connection, so we say no. But if we askis eight connected to nine? We are goingto say yes, even no we don't have a directconnection between eight and nine. Thereis a path from eight to three to four tonine. So, that's our problem, to be ableto officially support these two commandsfor given set of objects. Now, let's saywe add a union five, zero. So, thatcreates a connection between five andzero. Seven and two creates a connectionbetween seven and two. And six and one,between six and one. So, now if we ask ourzero connected to seven, well one and zerowe can do that too. And that's a redundantconnection. And now, if we ask is zeroconnected to seven we're going to answeryes. So that's our problem, intermixunion, commands and connected queries andwe need to be able to officially supportthose commands for a large number ofobjects. So, here's a much bigger example.And you can see that we're going to needefficient algorithms for this. First ofall, you can see we're going to need acomputer for this. It would take quite,quite some time for a human to figure outwhether there's a connection. In this casethere is a connection. Now, the algorithmsthat we're looking at today are not goingto actually give the path connecting thetwo objects. It's just going to be able toanswer the question, is there a path? Inpart two of the course, we'll consideralgorithms that explicitly find paths.They're not as efficient as union findbecause they have more work to do. Now,applications of these, these algorithmsinvolve objects of all types. These areused for digital photos, where the objectsare pixels they're used for networks,where the objects are computers, socialnetworks, where it's people, or computerchips, where it's circuit elements orabstract things like variable names in aprogram, or elements in a mathematicalset, or physical things like metallicsites in a composite system. So, alldifferent types of objects for, but forprogramming we're going to associate eachobject with a name and we'll just name theobjects with a number, integers from zeroto N-1. That's a very convenient initialstarting point for our programs because wecan use integers as an index into an arraythen, and then quickly access informationrelevant to each object. And it also justsupresses a lot of details that are notrelevant to union find. In fact, to makethis mapping from an object name to theinteger zero through N - one is to findapplication of a symbol table or asearching algorithm, which is one of thethings that we'll be studying later inthis course algorithms and data structuresfor solving that problem. Now, theconnections, well, we need, a few abstractproperties that these connections have tosatisfy. And they're all quite natural andintuitive. So we assume that is connectedto is an equivalence relation. That is,every object's connected to itself, it'ssymmetric. If P's connected to Q, then Q'sconnected to P, and it's transitive. IfP's connected to Q, and Q's connected toR, then P's connected to R. Now theseproperties are very intuitive. But it'sworthwhile to state them explicitly andmake sure that our algorithms maintainthem. When we have an equivalence relationa set of objects and connections divideinto subsets called connected components.A connected component is a maximal set ofobjects that's mutually connected. Forexample in this small example here,there's three connected components. Oneconsisting of just object zero, second oneobjects one, four and five. And third onethe other four objects. And thesecomponents have the property that if anytwo objects in them are connected andthere is no object outside that isconnected to those objects, that'sconnected components. Our algorithms willgain efficiency by maintaining connectedcomponents and using that knowledge toefficiently answer the query that's, thatthey're presented with. Okay, so toimplement the operations, we have to findquery and the union command. And so we'regoing to mai ntain the connectedcomponents. The find is going to have tocheck if two objects are in the samecomponent and the union command is goingto have to replace components containingtwo objects with their union. So, forexample, if we have these components, andwe get the command to union connect, twoand five. Essentially, we need to mergethe connected components containing theone containing two or the one containingfive to get a big connected components andnow we have only two connected components.All of that leads up to, in a programmingworld to specifying, a data type which issimply specification of the methods thatwe are want to going to implement in orderto solve this problem. So you know,typical Java model, what we will do iscreate a class called UF that contains twomethods, one to implement union, the otherone to implement connected, which returnsa boolean. The constructor, takes SR unit,the number of objects, so that it canbuild data structure based on the numberof objects. So, and we have to, bear inmind, as we're building our logarithms,that both the number of objects can behuge, but also, the number of operations.We can have a, a very large number, ofunion and connected, operations and ouralgorithms are going to have to beefficient, under those conditions. One ofthe practices that will follow often inthis course is to check our API designbefore getting too far into dealing withthe problem, by building a client that isgoing to use the data type that wedevelop. So, for this example, we've got aclient that, Will read information fromstandard input. First, an integer which isthe number of objects that are going to beprocessed. And then a series of pairs ofobject names. And what the client does isit, it'll, first it'll read the integerfrom standard input, and create a, a UFobject. And then as long as standard inputis not empty, it's going to read twointegers from the input. And if they'renot connected, then it'll connect them andprint them out. If they are connectedit'll ignore. So, that's our test clientand that's a fine test client to make surethat any implementation does what weexpect that it will. So, that's the setup.We've described the operations we want toimplement all the way down to code and wehave client code that we're going to haveto be able to service with our [ Pobierz całość w formacie PDF ]