1
00:00:01,140 --> 00:00:02,290
- Hey there.
2
00:00:02,290 --> 00:00:05,960
Welcome to week 11 of CS124 Online,
3
00:00:05,960 --> 00:00:08,203
Data Structures and Algorithms.
4
00:00:09,070 --> 00:00:12,890
Last week, we wrapped
up our study of hashing.
5
00:00:12,890 --> 00:00:14,963
Now we move on to some new topics.
6
00:00:16,280 --> 00:00:18,570
In our remaining time in this semester,
7
00:00:18,570 --> 00:00:21,940
we'll introduce the
dynamic equivalence problem
8
00:00:21,940 --> 00:00:23,720
and then we'll spend the rest of our time
9
00:00:23,720 --> 00:00:25,773
on graph algorithms and review.
10
00:00:27,040 --> 00:00:28,970
This week, we'll cover
some background material
11
00:00:28,970 --> 00:00:31,420
that we'll need for the
dynamic equivalence problem,
12
00:00:31,420 --> 00:00:34,640
specifically a quick
review of basic set theory,
13
00:00:34,640 --> 00:00:36,660
and then an introduction to relations,
14
00:00:36,660 --> 00:00:39,913
equivalence relations
and equivalence classes.
15
00:00:41,370 --> 00:00:43,770
Now, for these, we'll canonical example
16
00:00:43,770 --> 00:00:45,650
of congruence modulo n.
17
00:00:45,650 --> 00:00:47,440
What do I mean by that?
18
00:00:47,440 --> 00:00:52,250
Well, consider the set of all integers
19
00:00:52,250 --> 00:00:54,413
and then pick some number n.
20
00:00:55,430 --> 00:00:58,690
We can calculate each number modulo n,
21
00:00:58,690 --> 00:01:00,410
and the values that we're gonna get
22
00:01:00,410 --> 00:01:03,810
are gonna be from zero to one minus n.
23
00:01:03,810 --> 00:01:05,653
We can never get any other result.
24
00:01:06,610 --> 00:01:08,923
So let's say we let n equal three.
25
00:01:09,910 --> 00:01:11,890
No matter which integer we choose,
26
00:01:11,890 --> 00:01:14,570
the result of that integer module three
27
00:01:14,570 --> 00:01:17,490
must be one of zero, one, or two.
28
00:01:17,490 --> 00:01:19,333
No other result is possible.
29
00:01:20,200 --> 00:01:24,440
As we go from say zero, one,
two, three, four, and so on,
30
00:01:24,440 --> 00:01:28,410
our result will be zero,
one, two, zero, one, two,
31
00:01:28,410 --> 00:01:29,860
zero, one, two, and so on.
32
00:01:29,860 --> 00:01:31,423
It cycles to infinity.
33
00:01:32,460 --> 00:01:34,010
So with that information,
34
00:01:34,010 --> 00:01:36,740
we can classify the integers with respect
35
00:01:36,740 --> 00:01:38,710
to this operation.
36
00:01:38,710 --> 00:01:41,040
So there's one class of integers
37
00:01:41,040 --> 00:01:44,140
for which the result modulo three is zero.
38
00:01:44,140 --> 00:01:46,640
These are zero, three, six, nine, 12,
39
00:01:46,640 --> 00:01:48,473
the multiples of three and so on.
40
00:01:49,520 --> 00:01:51,280
Then there's another class
41
00:01:51,280 --> 00:01:54,460
for which the result modulo three is one.
42
00:01:54,460 --> 00:01:59,460
These are the number one,
four, seven, 10, 13, and so on.
43
00:02:00,520 --> 00:02:01,950
Finally, there's one more class
44
00:02:01,950 --> 00:02:04,680
for which the result modulo three is two.
45
00:02:04,680 --> 00:02:09,680
These are the numbers two,
five, eight, 11, 14, and so on.
46
00:02:11,430 --> 00:02:13,630
Every integer has got to be
47
00:02:13,630 --> 00:02:16,650
in one of those three classes
48
00:02:16,650 --> 00:02:20,023
and no integer can be in two
classes at the same time.
49
00:02:21,200 --> 00:02:24,410
And these are the equivalence
classes of the integers
50
00:02:24,410 --> 00:02:28,673
with respect to the relation
congruence modulo three.
51
00:02:29,760 --> 00:02:32,550
Notice that these sets are disjoint,
52
00:02:32,550 --> 00:02:34,800
that means that there's no element
53
00:02:34,800 --> 00:02:37,850
that's in two sets at the same time,
54
00:02:37,850 --> 00:02:40,130
and that they completely
divide up the integers.
55
00:02:40,130 --> 00:02:43,720
We call this a partition of the integers.
56
00:02:43,720 --> 00:02:46,370
And that's the basic idea
behind equivalence classes.
57
00:02:48,270 --> 00:02:49,180
Now, it turns out that there are
58
00:02:49,180 --> 00:02:50,920
a lot of other kinds of objects,
59
00:02:50,920 --> 00:02:53,430
not just integers that
have equivalence classes
60
00:02:53,430 --> 00:02:55,390
with respect to some equivalence relation.
61
00:02:55,390 --> 00:02:57,560
Yeah, sure, there's a lot in mathematics,
62
00:02:57,560 --> 00:03:00,350
but there are a lot out
in the real world too.
63
00:03:00,350 --> 00:03:02,920
For example, we can classify human beings
64
00:03:02,920 --> 00:03:04,470
with respect to their birthday.
65
00:03:05,620 --> 00:03:07,140
There's one equivalence class
66
00:03:07,140 --> 00:03:08,900
for each day of the year
67
00:03:08,900 --> 00:03:10,500
and each human being falls
68
00:03:10,500 --> 00:03:12,853
into exactly one equivalence class.
69
00:03:16,170 --> 00:03:17,690
These sets are disjoint.
70
00:03:17,690 --> 00:03:19,733
You can't have two different birthdays.
71
00:03:20,690 --> 00:03:23,590
Another example is electrical circuits,
72
00:03:23,590 --> 00:03:26,990
either two elements are
connected or they're not.
73
00:03:26,990 --> 00:03:29,150
Another example, siblings.
74
00:03:29,150 --> 00:03:30,713
That seems obvious, right?
75
00:03:31,620 --> 00:03:33,840
Another example, makes of cars.
76
00:03:33,840 --> 00:03:35,630
A car must be some make.
77
00:03:35,630 --> 00:03:37,470
It's either a Toyota, or a Ford,
78
00:03:37,470 --> 00:03:39,240
or a Ferrari, or whatever.
79
00:03:39,240 --> 00:03:43,270
And each car can be in
only one such class.
80
00:03:43,270 --> 00:03:45,790
There can't be a car
that's both a Volkswagen
81
00:03:45,790 --> 00:03:46,883
and a Honda.
82
00:03:48,860 --> 00:03:52,370
Anyhow, the dynamic
equivalence problem hinges
83
00:03:52,370 --> 00:03:55,493
on this notion of equivalence classes.
84
00:03:56,550 --> 00:03:59,110
The problem is easily stated.
85
00:03:59,110 --> 00:04:02,010
Given some set of objects
and some equivalence relation
86
00:04:02,010 --> 00:04:04,810
on these objects, how to we
design an algorithm that can,
87
00:04:04,810 --> 00:04:08,130
A, quickly determine if
two objects are equivalent
88
00:04:08,130 --> 00:04:11,490
with respect to the given relation, and B,
89
00:04:11,490 --> 00:04:14,470
quickly forge new
connections between objects
90
00:04:14,470 --> 00:04:17,370
by merging their equivalence classes?
91
00:04:17,370 --> 00:04:20,210
And we'll see that we can't
have our cake and eat it too.
92
00:04:20,210 --> 00:04:23,120
There's a trade off between
these two operations.
93
00:04:23,120 --> 00:04:25,750
This is a situation that's not uncommon
94
00:04:25,750 --> 00:04:28,140
when it comes to algorithm design.
95
00:04:28,140 --> 00:04:31,670
This is what we're gonna
learn with this problem,
96
00:04:31,670 --> 00:04:34,103
is what to do when we have a trade off.
97
00:04:35,320 --> 00:04:37,280
After we introduce this problem,
98
00:04:37,280 --> 00:04:40,110
we'll look at a number
of solutions next week,
99
00:04:40,110 --> 00:04:42,950
including some very clever
and surprisingly simple ways
100
00:04:42,950 --> 00:04:44,053
to speed things up.
101
00:04:45,260 --> 00:04:48,610
So to recap, this week
we've got set theory,
102
00:04:48,610 --> 00:04:51,250
relations, equivalence relations,
103
00:04:51,250 --> 00:04:54,190
equivalence classes, disjoint sets,
104
00:04:54,190 --> 00:04:57,510
and the statement of the
dynamic equivalence problem.
105
00:04:57,510 --> 00:04:59,920
So watch this week's video lectures
106
00:04:59,920 --> 00:05:03,080
and we'll have some coding
demonstrations next week.
107
00:05:03,080 --> 00:05:06,110
As always, these videos
and supplemental materials
108
00:05:06,110 --> 00:05:08,300
are posted here on Blackboard.
109
00:05:08,300 --> 00:05:09,840
And unlike most other weeks,
110
00:05:09,840 --> 00:05:12,253
there is no reading in
the textbook this week.
111
00:05:13,490 --> 00:05:14,810
At the end of this week, though,
112
00:05:14,810 --> 00:05:15,980
we'll have another quiz,
113
00:05:15,980 --> 00:05:17,580
which will cover this week's material
114
00:05:17,580 --> 00:05:20,840
and some additional material
we covered last week.
115
00:05:20,840 --> 00:05:22,320
And that's all for now.
116
00:05:22,320 --> 00:05:25,060
So I'll see you on our
Yellowdig discussion board.
117
00:05:25,060 --> 00:05:26,263
Thanks. Bye-bye.