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.