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.