- [Instructor] Okay, now we're gonna learn about
the dynamic equivalence problem.
The dynamic equivalence problem it presents
an interesting challenge.
It shows how there's a trade off when it comes
to designing an algorithm.
Say we have a collection of objects
and we'd like to be able to determine if two objects
are related to one another by some equivalence relation,
this is why we introduced to equivalence relations
a little earlier.
And we'd also like to be able to connect objects
by introducing an equivalents.
We'd also like to be able to perform both
of these operations as quickly and efficiently as possible.
This is the dynamic equivalence problem.
A common example is electrical connection.
Imagine we have certain electrical elements
and we can connect them by wires.
So here we have 12 elements labeled zero through 11.
And they're represented representatives nodes
and we have edges connecting them.
So we have these 12 elements, zero and six are connected
they belong to the same equivalence class.
Two, three and nine are connected, they belong to
the same equivalence class.
10 and 11 are connected, they belong to
the same equivalence class.
One, four, five, seven and eight stand alone each
in their own equivalence class.
So, why do we say these are equivalence classes?
Well, recall that an equivalence relation
is a relation that is reflexive, symmetric and transitive.
On this example any element that's we have here
is connected to itself, that's reflectivity.
So zero is connected to itself, one is connected to itself.
Now look at zero and six.
Clearly, zero is connected to six and six is connected
to zero that's symmetry.
Now look at two, three and nine.
Two is connected to three, three is connected to nine
and by transitivity two is connected to nine
and nine is connected to two, that's transitivity.
So, electrical connection here is a perfectly good example
of an equivalence relation, excuse me.
Now it's important to keep in mind that equivalency here
doesn't mean identity.
It means that the objects are equivalent with respect
to some relation in this case, it's electrical connection.
In another example we looked at congruence modular five.
So these are our equivalence classes
and notice that they form a partition.
Every element lies in exactly one equivalence class.
Also note that these are disjoint sets.
By disjoint we mean that the intersection of any two
of these sets indicated by the dash lines here
is empty, they're disjoint.
I'm also gonna introduce a term we'll see here later
in the course the connected component.
A connected component is a set
of nodes for which there exists
some path connecting each pair of nodes.
So in this example our equivalent classes
are connected components.
Since one is connected to itself there's trivially
a path that connects one to one.
Since zero and six are connected, there's a path
that connects six to zero and a path that connects
to zero to six happens to be the same path, that's okay.
There's of course here a path from two to nine passing
through three and from nine to two passing through three.
There's a path that connects 10 and 11 so we call
those connected components.
A standalone node can be a connected component too.
So each one of these sets is a disjoint set
and also a connected component.
So to get back to the dynamic equivalence problem we wanna
be able to do two things.
First, we wanna be able to determine
if elements are connected that is do they reside
in the same equivalence class.
And second, we want to be able to form connections
between elements that were not previously connected
and this will result in merging their equivalence classes.
We call the first operation find
and the second operation union.
So here find zero four we want to find out whether zero
and four are in the same equivalence class
and we see that they're not.
Four is sitting here by itself, zeros connected to six
but not to four.
So we'd want this query to return false.
In another example, find two and nine we'd want
this query to return true because two is connected
to nine two and nine are in the same equivalence class
in the same connected component.
So we'd want that to return true.
Now what about union three and eight?
Well, here we have the equivalence class that contains three
and the equivalence class that contains eight
and notice that these are disjoint.
There is no path connecting three and eight,
there is no connection here.
So, this union would create a connection where no connection
had previously existed.
So that would result in the merging
of those two equivalence classes
to form one larger equivalence class now containing two.
Three, eight, nine.
Again, we could refer to this as
a connected component now two, three, eight, nine.
For any two nodes in that component there's a path
that connects them, so it's connected component.
Now it turns out that we can optimize find
or optimize union to give us constant time performance
for either one of those operations.
But we cannot achieve constant time for both
with the same algorithm.
There's always a trade off and that's what makes
the dynamic equivalence problem so interesting.
And this is not at all unusual in the world
of data structures and algorithms.
We're often faced with trade-offs like this.
So what should we do?
Well, when considering design for this problem we'll need
to choose an appropriate data structure.
So what kind of data structure might we use?
Well, it's natural to think of a vector.
And here we have a vector that is of the appropriate size
and the indices correspond to each one of the elements
that we have here above.
But then what values do we use in our vector?
Well, one, seven, four and five the elements that sit
in their own equivalence classes that's easy.
We can just say the equivalence class for one is one,
for four it's four, for five it's five,
for seven it's seven.
They're alone in their equivalence class.
But what about the equivalence classes that contain more
than one element?
What would we do then?
Well, recall that we can choose a representative
for any equivalence class.
Because of reflexivity and transitivity it doesn't matter
which one we choose.
So for example, we could choose for this equivalence class
either zero or six could serve as a representative
of that class, it doesn't matter.
Let's choose six.
Then we put six here
in the vector position representing element zero
and we put six here.
There and then we can see that they're
in the same equivalence class because they both have
the same representative.
What do we do here, similarly we
can choose two, three, eight or nine to serve as
a representative of this equivalence class,
it doesn't matter.
Let's choose three.
And so now we populate these elements in our vector
with the value three.
And we can see that two, three, eight and nine all have
the same equivalence class because they have
the same representative.
And we can do the same thing for
the equivalence class containing 10 and 11.
We'll pick 11 and so now we have a vector which indicates
to which equivalents class each element belongs.
And we'll use this approach when we implement a solution
that optimizes for finding.
Later on we'll see another approach that we'll use
when we optimize for union.
But this should give you a good overview of what
the dynamic equivalence problem is, what questions
it's asking, what trade-offs are involved
and how we might choose a data structure that's appropriate
for this problem.
We'll see more in subsequent videos.
That's all for now.