The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

432 ratings

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 2

Kruskal's MST algorithm and applications to clustering; advanced union-find (optional).

- Tim RoughgardenProfessor

Computer Science

So, in this video, we're going to prove Tarjan's inverse Ackermann bound in the

Â performance of the union find data structure with union by rank and path

Â compression. Frankly, I hope you're kind of excited.

Â This is one of the crown jewels in the entire history of algorithms and data

Â structures. Let me remind you what the bound says.

Â You've got a union-find data structure, we're doing lazy unions, we're doing

Â union by rank, we're doing path compression.

Â And for an arbitrary sequence of m find a union operations. The total amount of

Â work you do over the sequence of operations is bounded above by m times

Â alpha of n, where n is the number of objects in the data structure and alpha

Â is the inverse Ackermann function that we defined in the previous video.

Â I want to give a shout out here to Dexter Kozen's beautiful book the Design and

Â Analysis of Algorithms. It is his analysis that I will be

Â following closely here. So, it's true that merely stating,

Â Tarjan's bound is non-trivial. We have this entire video defining the Ackermann

Â function and it's inverse so we could make sense of the statement.

Â That said, we're well positioned to approve Tarjan's bound.

Â In fact, the template of the proof is going to very much mirror what we already

Â did for the log star analysis by Hopcroft and Ullman.

Â So in that spirit, let's review what were the two basic workhorses, the two

Â building blocks that drove forward the Hopcroft-Ullman analysis.

Â So the first building block is the rank Lemma, which dates back all the way to

Â the videos pre-path compression. And remember the rank Lemma gives us

Â control on how many objects can exist with a given rank.

Â And in particular, that upper bound is decreasing exponentially with the rank,

Â it's n/2^r objects at most with the given rank r.

Â But, of course, we need a second building block to exploit the facts that we're

Â using the path compression optimization. So, how do we quantify the progress made

Â by path compression? Well, we argue that every time a node has

Â its parent pointer updated in path compression, it acquires a new parent

Â with strictly larger rank. So, you can think of the Hopcroft-Ullman

Â analysis as a clever and essentially optimal exploitation of these two

Â building blocks. How did we use them? Well, we define the

Â notion of rank blocks and each rank block has size to raise to the size of the

Â previous rank block. Why were rank blocks useful? Well, they

Â allowed us to measure progress as we followed parent pointers.

Â We defined an object to be good, if following it's parent, catapulted you

Â into a subsequent ranked block. Because there's only a log star number of

Â ranked blocks, you can only visit log star good nodes on any given find

Â operation. So, that gave us a per operation bound on

Â the log star for visits to good nodes. And then, for visits to bad nodes, we use

Â the second building block to argue that every time you visit a bad node, the rank

Â of its parent increases. And that can only happen so many times

Â before the rank of this object's parent is so much bigger than this object's rank

Â itself that the node has to be good. You have to make a lot of progress by

Â following its parent pointer. And the point is, if we want to do better

Â than the Hopcroft-Ullman analysis, we're not going to do better by taking these

Â same two building blocks and exploiting them in a better way, that can't be done.

Â So, what we need to do is have a better version of one of the two building

Â blocks. So, the key idea in Tarjan's analysis is

Â to have a stronger version of the second building block.

Â We're going to argue that path compression doesn't merely increase the

Â rank of nodes parents by one, but in fact, it increases typically the rank of

Â an object's parents by a lot. And what's kind of amazing is the link of

Â the proof we're about to do is really basically the same as that in the

Â Hopcroft-Ullman analysis. And the steps match up almost perfectly.

Â So, the bound is even better, the argument is even more ingenious.

Â It's even harder to imagine how one would come up with this idea oneself. But, as

Â far as checking it, as far as understanding it, the complexity level is

Â roughly the same as what we've already done in the log star analysis, so here we

Â go. So, in this slide, I'm going to give you

Â a definition. And the point of the definition is to

Â measure how much progress we make in terms of ranks when we follow a node's

Â parent pointer. So, the definition here is going to play exactly the same role

Â that the definition of rank blocks played in the Hopcroft-Ullman analysis.

Â So, what I'm going to define is a number, a statistic measuring the difference, the

Â gap, between the rank of an object and the rank of its parent. So, this

Â definition is only going to make sense for non-root objects x.

Â One thing I want you to remember from previous videos is that once an object is

Â not a root, it will never again be a root, and it's

Â rank will never again change. So, non-root objects have rank fixed

Â forevermore. So, we're going to use the notation delta

Â of x for the statistic. And the definition of delta of x is the largest

Â value of k such that a sub k, this is Ackermann function remember, such that a

Â sub k applied to the rank of this object x, is bounded above by the rank of x's

Â parent. So, the bigger the gap between the rank

Â of x's parent and x's rank, the bigger the value of delta of x.

Â So, let me mention, talk through some simple examples to make sure this makes

Â sense, and also review the Ackermann function a little bit.

Â So, first of all, let me just point out the delta of x is always non-negative for

Â any non-root object x. So, why is this true? Well remember, and

Â this goes all the way back to our union by rank discussion, the rank of an

Â object's parent is always at least one more than the rank of that object.

Â And the function a sub 0, recall we defined as the successor function.

Â So, for every object that's not a root, it's always true that it's parent has

Â rank at least one more than it. And that means we can always at least

Â take k to be zero and have the inequality be satisfied.

Â Now, when is it going to be true that an object x has a delta value at least equal

Â to one? Well, that is equivalent to stating we can take k to be 1 in this

Â inequality, and the inequality holds. So, let's remember what is the function a

Â sub one. In the previous video, we discovered that

Â was just the doubling function. So, we can take k=1 and have this

Â inequality satisfied if and only if the rank of the node's parent is at least

Â double the rank of that object. Similarly, an object x has a delta value

Â equal to at least 2 if and only if we can take k=2 on this right-hand side of the

Â definition and have this inequality be satisfied.

Â So, let's recall what the function a sub 2 is.

Â a sub 2 of r is just r*2^r. So, an object x has delta value equal to

Â 2 if and only if its parent's rank is substantially bigger than its own rank,

Â in the sense that if it has rank r, its parent's ranks has to be at least r*2^r.

Â And in general, the bigger the value of delta, the bigger the gap between the

Â rank of the object x and the rank of its parent.

Â And, of course, because the Ackermann function grows so ridiculously quickly,

Â the gap between this object's rank and its parent's rank is growing massively as

Â you take delta to be larger and larger. So, now that we understand this better,

Â one thing that should be clear is that the delta value of an object x can only

Â go up over time, right? So remember, we're talking only

Â about non-root objects x, so the x's rank itself, is frozen forevermore.

Â The only thing that's changing is it's acquiring potentially new parents,

Â through path compression, and each new parents rank is bigger than the previous

Â one. So, the gap in the ranks is only going

Â up, and therefore the delta value of this object x can only go up, over time.

Â So one final comment, you recall on the Hopcroft-Ullman analysis, the way we

Â defined rank blocks ensured that there weren't too many of them, there were only

Â log star. Similarly here, the way we're defining

Â the statistic delta, guarantees that there are not too many distinct delta

Â values that objects can take on. So, we've already argued that delta is a,

Â integer that's at least zero, and we can also bound it from above.

Â At least, for any object x that has a rank of at least 2, which will be good

Â enough for our purposes. If an object x has rank at least 2, its

Â value of delta can not be any larger than the inverse acromyn of n, than alpha of

Â n. And this is really just by the way we

Â define the inverse Ackermann function alpha, we defined it as the smallest

Â value of k such that if you apply a sub k to 2, that catapult to beyond end.

Â And since ranks of objects are bounded above by n, actually they're even bounded

Â above by log n but in particular by n that means you will never see a delta

Â value bigger that alpha of n for any object x has the rank at least two.

Â So, that completes the definition of the statistic data of x.

Â And, once again, the point of this statistic is to quantify progress through

Â rank space as we traverse a parent pointer, from an object.

Â So, in the Hopcroft-Ullman analysis, we used rank blocks for that purpose.

Â Here, we're using the statistic delta of x.

Â And now, we have to redefine good and bad objects to reflect this different

Â measurement for progress, for gaps between ranks of objects, and ranks of

Â their parents. So, that's what I'm going to provide for

Â you on this slide, the definition of good and bad nodes.

Â And, this definition will play exactly the same role as it did in the

Â Hopcroft-Ullman analysis. For the good nodes, we'll be able to just

Â get a per operation bound for how many visits we make to them. And then, we'll

Â be stuck with, and this will be the main part of the proof,

Â a global analysis arguing that the total number of visits to bad nodes over a

Â sequence of operations cannot be too big. So, the bad objects will be those that

Â meet the following set of four criteria. If an object fails to meet any of these

Â four criteria, it will be called good. So, the first two 2 criteria will be

Â familiar from the Hopcroft-Ullman analysis.

Â So, first of all, roots get a pass, and direct descendants of roots also get a

Â pass. So, to be bad, it must be the case you're

Â neither a root nor are you the child of a root.

Â So, what's the motivation for these two criteria? Well, it's exactly the same as

Â it was in the Hopcroft-Ullman analysis. It's just to ensure that bad nodes, after

Â they're visited on a find, get their parent pointer updated.

Â So remember, when you do path compression, after you've done a find

Â from an object x all the way up to its corresponding root, everybody's parent

Â pointer gets updated except for the root and except for the child of the root.

Â Those two nodes keep the same parent pointer.

Â So, to make sure we have progress, we want to exclude the root and the directed

Â sentence of the root from being bad, we'll acount for them separately.

Â The third criterion is not conceptually important, its just for technical

Â convenience sort of an out of factor the way I've defined the inverse arithmetic

Â function. We're going to give nodes that have rank

Â zero or one also with free paths. So, in order to bad, we're going to worry

Â about the case where the rank is at least 2.

Â So, the final criterion is really the ingenious one and it's the one that

Â ensures that when you do path compression typically objects parents ranks will

Â increase extremely rapidly, not just by 1.

Â And this criterion says, for an object x to be bad, it has to be the case that is

Â has some ancestor y. So, an object you get to by traversing

Â parent pointers from x, that has exactly the same value of delta.

Â So, if an object x has delta of x equal to 2, for it to be bad, there has to be

Â some ancestor object y that also has a delta value equal to 2.

Â And again, if x fails to meet any of these four conditions, then x gets a

Â pass, x is called a good object.

Â Now, I said that the role of this definition is going to be to split the

Â work done into two groups and that we're going to be able to easily bound, even on

Â a per operation basis, the number of visits to a good node.

Â So, the next quiz asks you to think about that carefully.

Â Alright. So, the correct answer is B. It's theta of the inverse Ackermann

Â function of n. And this is really one of the points, of

Â how we define good and bad nodes. We guarantee that there can not be too

Â many good nodes whenever we do a fine operation.

Â So, to see why this is true, let's just count up the number of nodes along a path

Â that can fail to meet each of the four criteria.

Â Well, so the first criterion was we give roots a free pass.

Â So there's at most one node, that's good because it's a root.

Â Similarly, on a given path there's at most one object on that path, it's a

Â direct descendant of the root. Because ranks always strictly go up when

Â you follow parent pointers that can be at most one object of rank zero and at most

Â one object of rank one. So, we, and most two objects get a free

Â pascals of the third criterion. Well, such thing about the interesting

Â case nodes that good be because they failed to meet the fourth criterion.

Â How many can that be? Well, let's focus on a particular value of delta.

Â So, let's say, think about all of the objects along a path that have delta of x

Â equal to 3. There may well be lots of objects on this

Â path with delta of x equal to 3, may be there's like 17 of them.

Â Call the highest to the closest to the root, such object z. Of these 17 objects

Â with delta of x equal to 3, z is going be the only one that is good.

Â The other 16 objects with delta of x equal to 3 are going to be bad.

Â Why? Well, any object other than z has an ancestor, namely z, with exactly the same

Â delta value. So that, those 16 objects do meet the

Â fourth criterion they will be classified as bad.

Â Summarizing for each of the alpha of n possible values, of delta, only the

Â upper-most object, the object closest to the root with that particular delta

Â value, can possibly be classified as good.

Â So, that bounds at alpha of n, the number of objects that fail to meet this fourth

Â criterion. That gives us the total bound of the

Â number of good nodes on any path.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.