1
00:00:01,380 --> 00:00:03,100
- [Instructor] Okay, now
we're gonna learn about

2
00:00:03,100 --> 00:00:05,100
the dynamic equivalence problem.

3
00:00:05,100 --> 00:00:07,880
The dynamic equivalence
problem it presents

4
00:00:07,880 --> 00:00:09,200
an interesting challenge.

5
00:00:09,200 --> 00:00:12,470
It shows how there's a
trade off when it comes

6
00:00:12,470 --> 00:00:14,760
to designing an algorithm.

7
00:00:14,760 --> 00:00:16,790
Say we have a collection of objects

8
00:00:17,900 --> 00:00:20,530
and we'd like to be able
to determine if two objects

9
00:00:20,530 --> 00:00:23,450
are related to one another
by some equivalence relation,

10
00:00:23,450 --> 00:00:25,830
this is why we introduced
to equivalence relations

11
00:00:25,830 --> 00:00:26,833
a little earlier.

12
00:00:27,940 --> 00:00:30,600
And we'd also like to be
able to connect objects

13
00:00:30,600 --> 00:00:32,463
by introducing an equivalents.

14
00:00:33,430 --> 00:00:35,280
We'd also like to be able to perform both

15
00:00:35,280 --> 00:00:39,860
of these operations as quickly
and efficiently as possible.

16
00:00:39,860 --> 00:00:42,333
This is the dynamic equivalence problem.

17
00:00:44,310 --> 00:00:47,650
A common example is electrical connection.

18
00:00:47,650 --> 00:00:50,500
Imagine we have certain
electrical elements

19
00:00:50,500 --> 00:00:53,000
and we can connect them by wires.

20
00:00:53,000 --> 00:00:58,000
So here we have 12 elements
labeled zero through 11.

21
00:00:58,540 --> 00:01:01,100
And they're represented
representatives nodes

22
00:01:01,100 --> 00:01:04,690
and we have edges connecting them.

23
00:01:04,690 --> 00:01:09,130
So we have these 12 elements,
zero and six are connected

24
00:01:09,130 --> 00:01:12,020
they belong to the same equivalence class.

25
00:01:12,020 --> 00:01:14,720
Two, three and nine are
connected, they belong to

26
00:01:14,720 --> 00:01:16,970
the same equivalence class.

27
00:01:16,970 --> 00:01:19,470
10 and 11 are connected, they belong to

28
00:01:19,470 --> 00:01:21,590
the same equivalence class.

29
00:01:21,590 --> 00:01:26,400
One, four, five, seven
and eight stand alone each

30
00:01:26,400 --> 00:01:28,540
in their own equivalence class.

31
00:01:28,540 --> 00:01:31,713
So, why do we say these
are equivalence classes?

32
00:01:33,140 --> 00:01:36,490
Well, recall that an equivalence relation

33
00:01:36,490 --> 00:01:40,793
is a relation that is reflexive,
symmetric and transitive.

34
00:01:41,660 --> 00:01:44,910
On this example any
element that's we have here

35
00:01:44,910 --> 00:01:47,380
is connected to itself,
that's reflectivity.

36
00:01:47,380 --> 00:01:51,113
So zero is connected to itself,
one is connected to itself.

37
00:01:52,460 --> 00:01:54,990
Now look at zero and six.

38
00:01:54,990 --> 00:01:59,210
Clearly, zero is connected
to six and six is connected

39
00:01:59,210 --> 00:02:01,053
to zero that's symmetry.

40
00:02:02,190 --> 00:02:05,770
Now look at two, three and nine.

41
00:02:05,770 --> 00:02:10,030
Two is connected to three,
three is connected to nine

42
00:02:10,030 --> 00:02:13,450
and by transitivity two
is connected to nine

43
00:02:13,450 --> 00:02:17,070
and nine is connected to
two, that's transitivity.

44
00:02:17,070 --> 00:02:21,010
So, electrical connection here
is a perfectly good example

45
00:02:21,010 --> 00:02:24,023
of an equivalence relation, excuse me.

46
00:02:26,150 --> 00:02:28,590
Now it's important to keep
in mind that equivalency here

47
00:02:28,590 --> 00:02:30,530
doesn't mean identity.

48
00:02:30,530 --> 00:02:33,410
It means that the objects
are equivalent with respect

49
00:02:33,410 --> 00:02:37,430
to some relation in this case,
it's electrical connection.

50
00:02:37,430 --> 00:02:40,803
In another example we looked
at congruence modular five.

51
00:02:41,680 --> 00:02:44,060
So these are our equivalence classes

52
00:02:44,060 --> 00:02:46,590
and notice that they form a partition.

53
00:02:46,590 --> 00:02:50,713
Every element lies in exactly
one equivalence class.

54
00:02:51,790 --> 00:02:55,320
Also note that these are disjoint sets.

55
00:02:55,320 --> 00:02:59,010
By disjoint we mean that
the intersection of any two

56
00:02:59,010 --> 00:03:01,740
of these sets indicated
by the dash lines here

57
00:03:01,740 --> 00:03:03,653
is empty, they're disjoint.

58
00:03:05,700 --> 00:03:08,520
I'm also gonna introduce a
term we'll see here later

59
00:03:08,520 --> 00:03:11,063
in the course the connected component.

60
00:03:12,050 --> 00:03:14,040
A connected component is a set

61
00:03:14,040 --> 00:03:15,830
of nodes for which there exists

62
00:03:15,830 --> 00:03:19,210
some path connecting each pair of nodes.

63
00:03:19,210 --> 00:03:21,980
So in this example our equivalent classes

64
00:03:21,980 --> 00:03:23,800
are connected components.

65
00:03:23,800 --> 00:03:27,140
Since one is connected to
itself there's trivially

66
00:03:27,140 --> 00:03:29,570
a path that connects one to one.

67
00:03:29,570 --> 00:03:34,570
Since zero and six are
connected, there's a path

68
00:03:34,900 --> 00:03:38,060
that connects six to zero
and a path that connects

69
00:03:38,060 --> 00:03:41,253
to zero to six happens to be
the same path, that's okay.

70
00:03:42,370 --> 00:03:45,470
There's of course here a
path from two to nine passing

71
00:03:45,470 --> 00:03:48,893
through three and from nine
to two passing through three.

72
00:03:49,800 --> 00:03:52,440
There's a path that connects
10 and 11 so we call

73
00:03:52,440 --> 00:03:54,250
those connected components.

74
00:03:54,250 --> 00:03:57,420
A standalone node can be
a connected component too.

75
00:03:57,420 --> 00:04:00,770
So each one of these
sets is a disjoint set

76
00:04:00,770 --> 00:04:02,583
and also a connected component.

77
00:04:03,530 --> 00:04:06,330
So to get back to the dynamic
equivalence problem we wanna

78
00:04:06,330 --> 00:04:08,860
be able to do two things.

79
00:04:08,860 --> 00:04:10,770
First, we wanna be able to determine

80
00:04:10,770 --> 00:04:13,650
if elements are connected
that is do they reside

81
00:04:13,650 --> 00:04:15,580
in the same equivalence class.

82
00:04:15,580 --> 00:04:18,240
And second, we want to be
able to form connections

83
00:04:18,240 --> 00:04:21,380
between elements that were
not previously connected

84
00:04:21,380 --> 00:04:24,333
and this will result in merging
their equivalence classes.

85
00:04:25,200 --> 00:04:27,610
We call the first operation find

86
00:04:27,610 --> 00:04:29,513
and the second operation union.

87
00:04:30,430 --> 00:04:35,430
So here find zero four we
want to find out whether zero

88
00:04:35,930 --> 00:04:38,970
and four are in the same equivalence class

89
00:04:38,970 --> 00:04:40,963
and we see that they're not.

90
00:04:42,170 --> 00:04:45,840
Four is sitting here by
itself, zeros connected to six

91
00:04:45,840 --> 00:04:47,570
but not to four.

92
00:04:47,570 --> 00:04:51,453
So we'd want this query to return false.

93
00:04:53,930 --> 00:04:58,090
In another example, find
two and nine we'd want

94
00:04:58,090 --> 00:05:02,010
this query to return true
because two is connected

95
00:05:02,010 --> 00:05:06,070
to nine two and nine are in
the same equivalence class

96
00:05:06,070 --> 00:05:08,100
in the same connected component.

97
00:05:08,100 --> 00:05:09,913
So we'd want that to return true.

98
00:05:12,750 --> 00:05:15,860
Now what about union three and eight?

99
00:05:15,860 --> 00:05:20,860
Well, here we have the equivalence
class that contains three

100
00:05:20,870 --> 00:05:23,550
and the equivalence
class that contains eight

101
00:05:23,550 --> 00:05:25,840
and notice that these are disjoint.

102
00:05:25,840 --> 00:05:28,530
There is no path
connecting three and eight,

103
00:05:28,530 --> 00:05:30,760
there is no connection here.

104
00:05:30,760 --> 00:05:35,760
So, this union would create a
connection where no connection

105
00:05:36,180 --> 00:05:38,350
had previously existed.

106
00:05:38,350 --> 00:05:41,090
So that would result in the merging

107
00:05:41,090 --> 00:05:43,380
of those two equivalence classes

108
00:05:43,380 --> 00:05:47,140
to form one larger equivalence
class now containing two.

109
00:05:47,140 --> 00:05:48,690
Three, eight, nine.

110
00:05:48,690 --> 00:05:50,210
Again, we could refer to this as

111
00:05:50,210 --> 00:05:53,760
a connected component now
two, three, eight, nine.

112
00:05:53,760 --> 00:05:58,040
For any two nodes in that
component there's a path

113
00:05:58,040 --> 00:06:00,440
that connects them, so
it's connected component.

114
00:06:01,870 --> 00:06:05,400
Now it turns out that we can optimize find

115
00:06:06,370 --> 00:06:10,280
or optimize union to give
us constant time performance

116
00:06:10,280 --> 00:06:13,240
for either one of those operations.

117
00:06:13,240 --> 00:06:17,150
But we cannot achieve
constant time for both

118
00:06:17,150 --> 00:06:18,930
with the same algorithm.

119
00:06:18,930 --> 00:06:21,410
There's always a trade
off and that's what makes

120
00:06:21,410 --> 00:06:24,240
the dynamic equivalence
problem so interesting.

121
00:06:24,240 --> 00:06:26,810
And this is not at all
unusual in the world

122
00:06:26,810 --> 00:06:29,250
of data structures and algorithms.

123
00:06:29,250 --> 00:06:31,960
We're often faced with
trade-offs like this.

124
00:06:31,960 --> 00:06:33,403
So what should we do?

125
00:06:35,610 --> 00:06:38,750
Well, when considering design
for this problem we'll need

126
00:06:38,750 --> 00:06:40,960
to choose an appropriate data structure.

127
00:06:40,960 --> 00:06:43,823
So what kind of data
structure might we use?

128
00:06:45,370 --> 00:06:48,330
Well, it's natural to think of a vector.

129
00:06:48,330 --> 00:06:53,330
And here we have a vector that
is of the appropriate size

130
00:06:53,860 --> 00:06:57,990
and the indices correspond
to each one of the elements

131
00:06:57,990 --> 00:07:00,753
that we have here above.

132
00:07:01,730 --> 00:07:04,793
But then what values do
we use in our vector?

133
00:07:08,260 --> 00:07:13,260
Well, one, seven, four and
five the elements that sit

134
00:07:13,730 --> 00:07:16,230
in their own equivalence
classes that's easy.

135
00:07:16,230 --> 00:07:21,230
We can just say the equivalence
class for one is one,

136
00:07:23,050 --> 00:07:25,360
for four it's four, for five it's five,

137
00:07:25,360 --> 00:07:26,523
for seven it's seven.

138
00:07:28,020 --> 00:07:30,320
They're alone in their equivalence class.

139
00:07:30,320 --> 00:07:33,120
But what about the equivalence
classes that contain more

140
00:07:33,120 --> 00:07:34,870
than one element?

141
00:07:34,870 --> 00:07:36,163
What would we do then?

142
00:07:37,490 --> 00:07:40,580
Well, recall that we can
choose a representative

143
00:07:40,580 --> 00:07:42,910
for any equivalence class.

144
00:07:42,910 --> 00:07:46,430
Because of reflexivity and
transitivity it doesn't matter

145
00:07:46,430 --> 00:07:48,350
which one we choose.

146
00:07:48,350 --> 00:07:53,030
So for example, we could choose
for this equivalence class

147
00:07:54,271 --> 00:07:57,420
either zero or six could
serve as a representative

148
00:07:57,420 --> 00:07:59,100
of that class, it doesn't matter.

149
00:07:59,100 --> 00:08:00,543
Let's choose six.

150
00:08:03,580 --> 00:08:05,110
Then we put six here

151
00:08:05,110 --> 00:08:08,330
in the vector position
representing element zero

152
00:08:08,330 --> 00:08:09,840
and we put six here.

153
00:08:09,840 --> 00:08:11,070
There and then we can see that they're

154
00:08:11,070 --> 00:08:13,460
in the same equivalence
class because they both have

155
00:08:13,460 --> 00:08:15,223
the same representative.

156
00:08:18,740 --> 00:08:20,780
What do we do here, similarly we

157
00:08:20,780 --> 00:08:24,240
can choose two, three,
eight or nine to serve as

158
00:08:24,240 --> 00:08:26,540
a representative of
this equivalence class,

159
00:08:26,540 --> 00:08:27,540
it doesn't matter.

160
00:08:27,540 --> 00:08:28,683
Let's choose three.

161
00:08:30,040 --> 00:08:33,810
And so now we populate
these elements in our vector

162
00:08:33,810 --> 00:08:35,500
with the value three.

163
00:08:35,500 --> 00:08:40,390
And we can see that two,
three, eight and nine all have

164
00:08:40,390 --> 00:08:42,270
the same equivalence
class because they have

165
00:08:42,270 --> 00:08:43,503
the same representative.

166
00:08:45,250 --> 00:08:46,580
And we can do the same thing for

167
00:08:46,580 --> 00:08:49,690
the equivalence class
containing 10 and 11.

168
00:08:49,690 --> 00:08:52,800
We'll pick 11 and so now we
have a vector which indicates

169
00:08:52,800 --> 00:08:56,250
to which equivalents class
each element belongs.

170
00:08:56,250 --> 00:08:59,160
And we'll use this approach
when we implement a solution

171
00:08:59,160 --> 00:09:00,963
that optimizes for finding.

172
00:09:02,150 --> 00:09:05,080
Later on we'll see another
approach that we'll use

173
00:09:05,080 --> 00:09:07,430
when we optimize for union.

174
00:09:07,430 --> 00:09:10,140
But this should give you
a good overview of what

175
00:09:10,140 --> 00:09:13,720
the dynamic equivalence
problem is, what questions

176
00:09:13,720 --> 00:09:16,490
it's asking, what trade-offs are involved

177
00:09:16,490 --> 00:09:19,780
and how we might choose a data
structure that's appropriate

178
00:09:19,780 --> 00:09:20,630
for this problem.

179
00:09:21,860 --> 00:09:23,620
We'll see more in subsequent videos.

180
00:09:23,620 --> 00:09:24,570
That's all for now.