1
00:00:00,760 --> 00:00:03,800
- [Instructor] Okay, so
we're gonna work our way
2
00:00:03,800 --> 00:00:06,350
toward the dynamic equivalence problem.
3
00:00:06,350 --> 00:00:07,510
And before we can do that
4
00:00:07,510 --> 00:00:09,652
we have to understand what are relations
5
00:00:09,652 --> 00:00:12,049
and equivalence relations.
6
00:00:12,049 --> 00:00:16,066
And you'll recall that when
we first presented sorting
7
00:00:16,066 --> 00:00:20,810
we discussed order
relations and we used the
8
00:00:20,810 --> 00:00:25,810
less than or equal to
operator as an example.
9
00:00:25,910 --> 00:00:29,502
And we saw that if we apply
that operator to the integers
10
00:00:29,502 --> 00:00:33,120
then we see that it's reflexive.
11
00:00:33,120 --> 00:00:36,370
That is A is less than or equal to A
12
00:00:36,370 --> 00:00:38,926
for all A and the
integers that makes sense.
13
00:00:38,926 --> 00:00:40,761
It's anti symmetric.
14
00:00:40,761 --> 00:00:45,190
That is if A is less than or equal to B
15
00:00:45,190 --> 00:00:49,485
and B is less than or equal
to A, then A's got an equal B.
16
00:00:49,485 --> 00:00:53,920
And it's transitive, if A
is less than or equal to B
17
00:00:53,920 --> 00:00:55,670
and B is less than equal to C
18
00:00:55,670 --> 00:01:00,195
then A is less than or
equal to C so far so good.
19
00:01:00,195 --> 00:01:03,160
But what we wanna do is
we wanna take a step back
20
00:01:03,160 --> 00:01:05,279
and look at relations in general.
21
00:01:05,279 --> 00:01:08,040
And then we're going
to move on to the idea
22
00:01:08,040 --> 00:01:09,500
of an equivalence relation
23
00:01:09,500 --> 00:01:11,623
which is different from an order relation.
24
00:01:12,820 --> 00:01:13,965
Now, what is a relation?
25
00:01:13,965 --> 00:01:17,172
Let's say we have two sets A and B
26
00:01:17,172 --> 00:01:20,650
and we have an element from each set.
27
00:01:20,650 --> 00:01:23,464
We'll call those lower
case a and lowercase b.
28
00:01:23,464 --> 00:01:26,940
And we say that these a and b are related
29
00:01:26,940 --> 00:01:31,200
if the pair that's an ordered
pair, a b is an element
30
00:01:31,200 --> 00:01:34,430
of the set S where S is a subset
31
00:01:34,430 --> 00:01:37,713
of the Cartesian product of sets a and b.
32
00:01:38,670 --> 00:01:40,273
That's a mouthful.
33
00:01:40,273 --> 00:01:42,461
So let's unpack this.
34
00:01:42,461 --> 00:01:46,900
First we need to understand
what is a Cartesian product.
35
00:01:46,900 --> 00:01:48,670
A really good example
36
00:01:48,670 --> 00:01:51,150
of a Cartesian product is playing cards.
37
00:01:51,150 --> 00:01:52,440
We've all seen playing cards.
38
00:01:52,440 --> 00:01:57,440
It's 52 of them, and
we have a set of ranks.
39
00:01:58,443 --> 00:02:03,068
Every suit has each one of these ranks.
40
00:02:03,068 --> 00:02:05,610
And then we have a set of suits.
41
00:02:05,610 --> 00:02:07,180
They're are four of those.
42
00:02:07,180 --> 00:02:12,180
So we have the ACE of clubs,
the ACE of diamonds, the ACE
43
00:02:12,740 --> 00:02:17,404
of spades, the ACE of hearts,
the two of clubs, and so on.
44
00:02:17,404 --> 00:02:18,874
You see what I'm doing?
45
00:02:18,874 --> 00:02:21,598
I'm taking every item in this set
46
00:02:21,598 --> 00:02:25,726
and pairing it with one item in this set
47
00:02:25,726 --> 00:02:28,573
but I'm doing it for all possible pairs.
48
00:02:28,573 --> 00:02:32,430
Now we've got 13 elements
49
00:02:32,430 --> 00:02:36,050
in this set and four elements in this set.
50
00:02:36,050 --> 00:02:38,780
So the Cartesian product, when we take all
51
00:02:38,780 --> 00:02:42,280
of those possible pairs is gonna be 52.
52
00:02:42,280 --> 00:02:45,090
That's gonna get us our deck of cards.
53
00:02:45,090 --> 00:02:49,596
So the set of all playing
cards is the set of all ranks.
54
00:02:49,596 --> 00:02:54,444
And I'm gonna say, cross
the set of all suits.
55
00:02:54,444 --> 00:02:58,630
Now this x, I say cross,
because that's what we're doing
56
00:03:00,051 --> 00:03:03,420
when we're generating
these pairs from these sets
57
00:03:03,420 --> 00:03:07,540
it's meant to have a connotation
similar to multiplication.
58
00:03:07,540 --> 00:03:09,440
And that's of course implied
59
00:03:09,440 --> 00:03:13,390
in the term Cartesian product,
but we're not multiplying.
60
00:03:13,390 --> 00:03:16,230
You can think of it as
a overloaded operator
61
00:03:16,230 --> 00:03:20,749
which it is we're taking
all of the possible pairs.
62
00:03:20,749 --> 00:03:22,020
So we do that.
63
00:03:22,020 --> 00:03:23,337
We get this set, we get this set
64
00:03:23,337 --> 00:03:26,209
and we can generate from
that all possible pairs.
65
00:03:26,209 --> 00:03:30,840
And we have our complete deck
of playing cards here, right?
66
00:03:30,840 --> 00:03:32,633
That's a Cartesian product.
67
00:03:33,690 --> 00:03:37,318
So let's go back to the
relations here for a second.
68
00:03:37,318 --> 00:03:39,540
And let's read it again.
69
00:03:39,540 --> 00:03:42,890
Let's say we have two sets A
and B and we have an element
70
00:03:42,890 --> 00:03:45,280
from each set, little a and little b,
71
00:03:45,280 --> 00:03:47,580
and we say that little
a and little b related
72
00:03:47,580 --> 00:03:49,501
if the pair little a b is an element
73
00:03:49,501 --> 00:03:53,540
of the set S with S being a subset
74
00:03:53,540 --> 00:03:57,302
of the Cartesian product
of the sets, a and b.
75
00:03:57,302 --> 00:03:59,814
So in the case of playing
cards, that might be
76
00:03:59,814 --> 00:04:02,328
we have two cards are related.
77
00:04:02,328 --> 00:04:05,390
Maybe if their suit is the same
78
00:04:05,390 --> 00:04:07,280
or if their rank is the same
79
00:04:07,280 --> 00:04:11,332
or if their rank is even for example
80
00:04:11,332 --> 00:04:16,070
and that would be a subset of
the Cartesian product of sets.
81
00:04:16,070 --> 00:04:16,903
Okay?
82
00:04:17,770 --> 00:04:20,757
So that's our example of playing cards.
83
00:04:20,757 --> 00:04:23,450
But it needn't be playing cards,
84
00:04:23,450 --> 00:04:26,710
we could take any two
sets, set a and set b
85
00:04:26,710 --> 00:04:29,683
and we could take all
of the possible pairs
86
00:04:29,683 --> 00:04:32,510
of elements taking the first element
87
00:04:32,510 --> 00:04:35,279
from the set a and the
second element from the set b
88
00:04:35,279 --> 00:04:37,700
and we can generate the Cartesian product
89
00:04:37,700 --> 00:04:39,423
on two arbitrary sets.
90
00:04:40,898 --> 00:04:45,220
It's not unusual that a
and b are the same set.
91
00:04:45,220 --> 00:04:47,910
Here A and B are both a
set of natural numbers.
92
00:04:47,910 --> 00:04:49,860
Those are the counting numbers.
93
00:04:49,860 --> 00:04:51,838
And this set, the Cartesian product
94
00:04:51,838 --> 00:04:54,988
of N cross N is
95
00:04:54,988 --> 00:04:58,390
one one, one two,
96
00:04:58,390 --> 00:05:00,380
one three, one four
97
00:05:00,380 --> 00:05:05,270
off to infinity there, two one,
two two, two three, two four
98
00:05:05,270 --> 00:05:08,470
off to infinity three one, and so on.
99
00:05:08,470 --> 00:05:10,580
That's the Cartesian product
100
00:05:10,580 --> 00:05:14,778
of the natural numbers
and the natural numbers.
101
00:05:14,778 --> 00:05:18,480
But remember, let's go
back to this one again.
102
00:05:18,480 --> 00:05:20,130
I'm gonna go back to it again.
103
00:05:20,130 --> 00:05:21,623
We're gonna look at S being a subset
104
00:05:21,623 --> 00:05:24,028
of the Cartesian product.
105
00:05:24,028 --> 00:05:28,890
So here's a subset, we've got one one,
106
00:05:28,890 --> 00:05:33,520
two four, three nine, four 16, five 25.
107
00:05:33,520 --> 00:05:37,603
That's clearly a subset
of the cross of N by N,
108
00:05:38,766 --> 00:05:40,394
what generates this?
109
00:05:40,394 --> 00:05:45,394
What function gives us this
subset of the Cartesian product
110
00:05:46,240 --> 00:05:47,750
of N cross N?
111
00:05:47,750 --> 00:05:51,263
Well, it's the function
F of X equals X squared.
112
00:05:51,263 --> 00:05:54,570
One squared is one, two squared is four
113
00:05:54,570 --> 00:05:57,883
three squared is nine, four
squared to 16 and so on.
114
00:05:58,936 --> 00:06:03,010
Here's another one, we have this subset
115
00:06:03,010 --> 00:06:06,850
one two, two three, three
four, four five, five six,
116
00:06:06,850 --> 00:06:07,830
and so on.
117
00:06:07,830 --> 00:06:11,067
That's clearly a subset
of the Cartesian product
118
00:06:11,067 --> 00:06:12,637
of N cross N.
119
00:06:12,637 --> 00:06:14,930
And it's generated by this function
120
00:06:14,930 --> 00:06:16,850
F of X equals X plus one.
121
00:06:16,850 --> 00:06:18,822
We often call that the successor function.
122
00:06:18,822 --> 00:06:21,560
So one plus one is two
123
00:06:21,560 --> 00:06:24,100
two plus one is three,
three, plus one is four.
124
00:06:24,100 --> 00:06:24,933
And so on.
125
00:06:27,170 --> 00:06:28,350
Here's another one.
126
00:06:28,350 --> 00:06:31,500
Take a look at this and tell
me if you can figure out
127
00:06:31,500 --> 00:06:35,190
what the function is that
generates this subset
128
00:06:35,190 --> 00:06:37,610
one one, two two, three three, four four,
129
00:06:37,610 --> 00:06:41,410
five zero, six one, seven
two, eight three, nine four,
130
00:06:41,410 --> 00:06:44,351
10 zero, 11 one.
131
00:06:44,351 --> 00:06:49,351
Yup, F of X equals X mod five.
132
00:06:51,010 --> 00:06:55,180
So one mod five is one,
two mod five is two,
133
00:06:55,180 --> 00:06:57,606
three mod five is three,
four mod five is four
134
00:06:57,606 --> 00:07:00,980
five mod five is zero,
six mod five is one.
135
00:07:00,980 --> 00:07:02,297
And so on.
136
00:07:02,297 --> 00:07:03,660
Guess what?
137
00:07:03,660 --> 00:07:07,176
We're gonna see this example again.
138
00:07:07,176 --> 00:07:12,176
So I hope we've unpacked
this paragraph a little bit.
139
00:07:13,097 --> 00:07:15,669
Again, we have two sets A and B,
140
00:07:15,669 --> 00:07:18,980
we take an element from each set, A and B,
141
00:07:18,980 --> 00:07:21,590
and we say that A and B are related
142
00:07:21,590 --> 00:07:25,420
if the pair is an element of the set S
143
00:07:25,420 --> 00:07:28,723
with S being a subset of the
Cartesian product of the sets
144
00:07:28,723 --> 00:07:33,723
A and B, and put another
way, quote, this is
145
00:07:34,740 --> 00:07:38,380
from a book by Mark Alan
Weiss called data structures
146
00:07:38,380 --> 00:07:40,670
and algorithms in Java.
147
00:07:40,670 --> 00:07:43,822
A relation R is defined on a set S
148
00:07:43,822 --> 00:07:48,084
if for every pair of the elements, A and B
149
00:07:48,084 --> 00:07:53,084
with a and B elements of S a
R b is either true or false.
150
00:07:54,820 --> 00:07:59,729
So here, this a R b is a way
of writing a is related to b.
151
00:07:59,729 --> 00:08:02,650
Okay. And it's either true or false.
152
00:08:02,650 --> 00:08:04,382
There's a predicate involved here.
153
00:08:04,382 --> 00:08:09,382
And if a R b is true, then we
say that a is related to b.
154
00:08:09,723 --> 00:08:12,235
So those are relations.
155
00:08:12,235 --> 00:08:14,697
Now what's an equivalence relation.
156
00:08:14,697 --> 00:08:17,080
Well, if you'll remember again,
157
00:08:17,080 --> 00:08:20,430
we looked at some properties
of order relations,
158
00:08:20,430 --> 00:08:22,920
for example, they're anti symmetric.
159
00:08:22,920 --> 00:08:26,080
Well, an equivalence
relation is a relation
160
00:08:26,080 --> 00:08:31,080
which is reflexive,
symmetric, and transitive.
161
00:08:31,293 --> 00:08:33,197
We have all three of those apply.
162
00:08:33,197 --> 00:08:37,353
Then our relation is an
equivalence relation.
163
00:08:37,353 --> 00:08:39,430
What does that mean?
164
00:08:39,430 --> 00:08:42,901
Well, a is related to itself
that seems almost obvious.
165
00:08:42,901 --> 00:08:47,901
That is a is related to
a, for all a and S, okay.
166
00:08:48,412 --> 00:08:51,125
What does it mean to be symmetric?
167
00:08:51,125 --> 00:08:55,350
Well, if a is related to
b, then b is related to a
168
00:08:55,350 --> 00:08:59,012
that seems pretty straight forward too.
169
00:08:59,012 --> 00:09:02,680
And transitivity should
come as no surprise.
170
00:09:02,680 --> 00:09:05,759
If a is related to b,
and b is related to c,
171
00:09:05,759 --> 00:09:08,271
then a is related to c.
172
00:09:08,271 --> 00:09:11,710
Now we're using this R
notation, but sometimes
173
00:09:11,710 --> 00:09:15,680
you'll see this written
with a Tilde same thing.
174
00:09:15,680 --> 00:09:18,791
Don't be surprised to see that notation.
175
00:09:18,791 --> 00:09:22,960
Now let's talk about equivalence classes.
176
00:09:22,960 --> 00:09:25,770
Now, given some relation R we can speak
177
00:09:25,770 --> 00:09:29,030
of equivalence classes with respect to r.
178
00:09:29,030 --> 00:09:32,923
And we just saw the example
of congruence mod five
179
00:09:32,923 --> 00:09:36,076
we'll have five equivalence classes.
180
00:09:36,076 --> 00:09:41,076
Let's say we have some number
a with a mod five equal one.
181
00:09:41,401 --> 00:09:45,710
We write the equivalence
class represented by a
182
00:09:45,710 --> 00:09:47,610
as a in square brackets.
183
00:09:47,610 --> 00:09:52,610
So this means all of the
things that are equivalent to a
184
00:09:53,974 --> 00:09:57,272
with regard to some relation.
185
00:09:57,272 --> 00:10:01,498
All right, in this case,
mod five equals one.
186
00:10:01,498 --> 00:10:06,498
A number is in this same
class as a, if it is congruent
187
00:10:06,940 --> 00:10:11,940
to a mod five what's in this
class, well, one, six, 11.
188
00:10:14,180 --> 00:10:19,180
Okay. And generally we can
write the equivalence class
189
00:10:20,510 --> 00:10:24,550
that's represented by a equals all the X
190
00:10:24,550 --> 00:10:29,550
in S such that X is related
to a let's look at an example.
191
00:10:30,900 --> 00:10:33,636
We're gonna stick with
congruence modulo five.
192
00:10:33,636 --> 00:10:36,434
So here we have some numbers.
193
00:10:36,434 --> 00:10:39,930
We have zero mod five
zero, one mod five is one,
194
00:10:39,930 --> 00:10:42,227
two mod five is two and so on.
195
00:10:42,227 --> 00:10:44,410
And you can see that some
196
00:10:44,410 --> 00:10:47,890
of these are equivalent they're congruent
197
00:10:47,890 --> 00:10:51,260
modulo five, zero and five for example,
198
00:10:51,260 --> 00:10:54,280
one in six are congruent modulo five,
199
00:10:54,280 --> 00:10:57,058
two and seven are congruent modulo five,
200
00:10:57,058 --> 00:11:00,600
three and eight are congruent modulo five,
201
00:11:00,600 --> 00:11:03,890
four and nine are congruent modulo five.
202
00:11:03,890 --> 00:11:04,975
And so on.
203
00:11:04,975 --> 00:11:09,729
Now, an interesting property
of equivalence classes
204
00:11:09,729 --> 00:11:14,420
is they completely partition
the set in question,
205
00:11:14,420 --> 00:11:18,040
for example, we here we have the set A Z
206
00:11:18,040 --> 00:11:20,146
is the set of all integers
207
00:11:20,146 --> 00:11:23,810
and we have five nice tidy slices.
208
00:11:23,810 --> 00:11:27,086
And each slice has its own representative.
209
00:11:27,086 --> 00:11:30,560
This is all the X element of Z
210
00:11:30,560 --> 00:11:35,282
where X is congruent to zero modulo five.
211
00:11:35,282 --> 00:11:39,360
That's these orange guys here fall
212
00:11:39,360 --> 00:11:41,765
in this orange slice here.
213
00:11:41,765 --> 00:11:45,206
These are all the ones that
are congruent to one mod five
214
00:11:45,206 --> 00:11:49,010
all the elements of Z that are congruent
215
00:11:49,010 --> 00:11:53,260
to two mod five, to three
mod five, to four by five.
216
00:11:53,260 --> 00:11:54,605
There's nothing else.
217
00:11:54,605 --> 00:11:57,262
If you take any number mod five
218
00:11:57,262 --> 00:12:00,420
you're only gonna get one
of these five answers,
219
00:12:00,420 --> 00:12:02,820
zero, one, two, three, or four.
220
00:12:02,820 --> 00:12:06,505
So any number any integer
is gonna be congruent
221
00:12:06,505 --> 00:12:11,505
either to zero, to one, to
two, to three or to four,
222
00:12:11,638 --> 00:12:14,090
with respect to mod five.
223
00:12:14,090 --> 00:12:16,219
Notice also that these sets are disjoint.
224
00:12:16,219 --> 00:12:18,600
What does it mean to be disjoint?
225
00:12:18,600 --> 00:12:21,722
Well, remember what we saw
in our introduction to sets
226
00:12:21,722 --> 00:12:25,211
it means that their intersection is empty.
227
00:12:25,211 --> 00:12:28,374
That means that there can't be any element
228
00:12:28,374 --> 00:12:32,490
in the integers that's in this set.
229
00:12:32,490 --> 00:12:36,248
And also in this set or any other set.
230
00:12:36,248 --> 00:12:38,450
If it's congruent to zero,
231
00:12:38,450 --> 00:12:41,390
it's only congruent to zero mod five.
232
00:12:41,390 --> 00:12:45,033
It also can't be congruent to two mod five
233
00:12:45,033 --> 00:12:49,030
every number is in its own bin.
234
00:12:49,030 --> 00:12:53,583
And those sets are disjoint
and they form a partition.
235
00:12:53,583 --> 00:12:58,583
All of Z is in one of these five sets.
236
00:12:58,622 --> 00:13:03,622
And each element in Z is in
exactly one of these sets.
237
00:13:05,072 --> 00:13:08,023
And that's an equivalence class.
238
00:13:09,440 --> 00:13:10,880
Here's some examples.
239
00:13:10,880 --> 00:13:14,192
Obviously we've just been
looking at Congress modulo N
240
00:13:14,192 --> 00:13:18,173
that's going to generate
equivalence classes for us.
241
00:13:19,100 --> 00:13:22,143
Are hash values are equivalence classes.
242
00:13:23,299 --> 00:13:27,420
Similar triangles or congruent triangles
243
00:13:27,420 --> 00:13:31,820
represent equivalence classes,
cities within countries,
244
00:13:31,820 --> 00:13:35,405
all the cities in France
are within France.
245
00:13:35,405 --> 00:13:37,017
They're not within Spain.
246
00:13:37,017 --> 00:13:40,119
And all cities are within some country.
247
00:13:40,119 --> 00:13:42,290
Yes, there are some city States
248
00:13:42,290 --> 00:13:45,575
but then the city is the
country like Monaco for example.
249
00:13:45,575 --> 00:13:49,940
The countries are the equivalents
classes that partition
250
00:13:49,940 --> 00:13:51,283
the set of all cities.
251
00:13:53,050 --> 00:13:56,892
Birthdays another good example,
we all have a birthday.
252
00:13:56,892 --> 00:13:58,985
Some of us have the same birthday.
253
00:13:58,985 --> 00:14:00,812
None of us have two birthdays.
254
00:14:00,812 --> 00:14:04,188
You can imagine the population of earth
255
00:14:04,188 --> 00:14:09,010
all partitioned into sets
based on their birthday.
256
00:14:09,010 --> 00:14:11,170
Everybody that was born on January 1st
257
00:14:11,170 --> 00:14:14,113
everybody that was born
on January 2nd and so on.
258
00:14:15,150 --> 00:14:18,318
What are some non-examples
order relations?
259
00:14:18,318 --> 00:14:23,160
Why aren't order relations
equivalence classes?
260
00:14:23,160 --> 00:14:26,020
Well, because they're not symmetric.
261
00:14:26,020 --> 00:14:29,403
If A is less than B than
B is not less than A.
262
00:14:30,880 --> 00:14:34,230
Students and course registration at UVM.
263
00:14:34,230 --> 00:14:36,880
Well, those aren't equivalent classes
264
00:14:36,880 --> 00:14:40,457
because students can register
for more than one class.
265
00:14:40,457 --> 00:14:43,090
And the classes that they've
registered don't partition
266
00:14:43,090 --> 00:14:43,923
the students.
267
00:14:45,080 --> 00:14:47,980
Dog breeds. Well, we have mixed breeds.
268
00:14:47,980 --> 00:14:50,830
We have cockapoos that are
a mix of cocker, spaniels
269
00:14:50,830 --> 00:14:53,390
and poodles are
labradoodles, which are mixes
270
00:14:53,390 --> 00:14:55,910
of labrador, retrievers,
and poodles and so on.
271
00:14:55,910 --> 00:14:58,169
And finally friendship.
272
00:14:58,169 --> 00:15:01,164
Friendship. What's the
problem with friendship?
273
00:15:01,164 --> 00:15:03,532
It's not transitive.
274
00:15:03,532 --> 00:15:06,500
Abby can be a friend of Joe.
275
00:15:06,500 --> 00:15:08,120
Joe can be a friend of Lisa
276
00:15:08,120 --> 00:15:10,700
but that doesn't mean that
Lisa and Abby are friends.
277
00:15:10,700 --> 00:15:13,550
It's not transitive and
therefore it's not an equivalent.
278
00:15:14,528 --> 00:15:17,760
So this should give you an overview
279
00:15:17,760 --> 00:15:19,720
of what are equivalence classes.
280
00:15:19,720 --> 00:15:21,230
And from here, we're gonna move on to
281
00:15:21,230 --> 00:15:23,570
the dynamic equivalence problem.
282
00:15:23,570 --> 00:15:26,423
We'll see that in a later
video, that's all for now.