- Hey there.
Welcome to week 11 of CS124 Online,
Data Structures and Algorithms.
Last week, we wrapped up our study of hashing.
Now we move on to some new topics.
In our remaining time in this semester,
we'll introduce the dynamic equivalence problem
and then we'll spend the rest of our time
on graph algorithms and review.
This week, we'll cover some background material
that we'll need for the dynamic equivalence problem,
specifically a quick review of basic set theory,
and then an introduction to relations,
equivalence relations and equivalence classes.
Now, for these, we'll canonical example
of congruence modulo n.
What do I mean by that?
Well, consider the set of all integers
and then pick some number n.
We can calculate each number modulo n,
and the values that we're gonna get
are gonna be from zero to one minus n.
We can never get any other result.
So let's say we let n equal three.
No matter which integer we choose,
the result of that integer module three
must be one of zero, one, or two.
No other result is possible.
As we go from say zero, one, two, three, four, and so on,
our result will be zero, one, two, zero, one, two,
zero, one, two, and so on.
It cycles to infinity.
So with that information,
we can classify the integers with respect
to this operation.
So there's one class of integers
for which the result modulo three is zero.
These are zero, three, six, nine, 12,
the multiples of three and so on.
Then there's another class
for which the result modulo three is one.
These are the number one, four, seven, 10, 13, and so on.
Finally, there's one more class
for which the result modulo three is two.
These are the numbers two, five, eight, 11, 14, and so on.
Every integer has got to be
in one of those three classes
and no integer can be in two classes at the same time.
And these are the equivalence classes of the integers
with respect to the relation congruence modulo three.
Notice that these sets are disjoint,
that means that there's no element
that's in two sets at the same time,
and that they completely divide up the integers.
We call this a partition of the integers.
And that's the basic idea behind equivalence classes.
Now, it turns out that there are
a lot of other kinds of objects,
not just integers that have equivalence classes
with respect to some equivalence relation.
Yeah, sure, there's a lot in mathematics,
but there are a lot out in the real world too.
For example, we can classify human beings
with respect to their birthday.
There's one equivalence class
for each day of the year
and each human being falls
into exactly one equivalence class.
These sets are disjoint.
You can't have two different birthdays.
Another example is electrical circuits,
either two elements are connected or they're not.
Another example, siblings.
That seems obvious, right?
Another example, makes of cars.
A car must be some make.
It's either a Toyota, or a Ford,
or a Ferrari, or whatever.
And each car can be in only one such class.
There can't be a car that's both a Volkswagen
and a Honda.
Anyhow, the dynamic equivalence problem hinges
on this notion of equivalence classes.
The problem is easily stated.
Given some set of objects and some equivalence relation
on these objects, how to we design an algorithm that can,
A, quickly determine if two objects are equivalent
with respect to the given relation, and B,
quickly forge new connections between objects
by merging their equivalence classes?
And we'll see that we can't have our cake and eat it too.
There's a trade off between these two operations.
This is a situation that's not uncommon
when it comes to algorithm design.
This is what we're gonna learn with this problem,
is what to do when we have a trade off.
After we introduce this problem,
we'll look at a number of solutions next week,
including some very clever and surprisingly simple ways
to speed things up.
So to recap, this week we've got set theory,
relations, equivalence relations,
equivalence classes, disjoint sets,
and the statement of the dynamic equivalence problem.
So watch this week's video lectures
and we'll have some coding demonstrations next week.
As always, these videos and supplemental materials
are posted here on Blackboard.
And unlike most other weeks,
there is no reading in the textbook this week.
At the end of this week, though,
we'll have another quiz,
which will cover this week's material
and some additional material we covered last week.
And that's all for now.
So I'll see you on our Yellowdig discussion board.
Thanks. Bye-bye.