1 00:00:03,040 --> 00:00:07,406 In this optional video, I'm going to give you a glimpse of the research frontier on 2 00:00:07,406 --> 00:00:11,000 the problem of computing Minimum Cost, Spanning Trees. 3 00:00:11,000 --> 00:00:14,051 We've now seen two excellent algorithms for this problem. 4 00:00:14,051 --> 00:00:18,227 Prim's algorithm and Kruskal's algorithm. And we had suitable data structures both 5 00:00:18,227 --> 00:00:21,493 running near linear time. Big O of M Log N, where M is the number 6 00:00:21,493 --> 00:00:23,474 of edges, N is the number of vertices. 7 00:00:23,474 --> 00:00:26,901 Now going ahead we should be pretty happy with those algorithms. 8 00:00:26,901 --> 00:00:30,541 We're only a log factor slower than what it takes to read the input. 9 00:00:30,541 --> 00:00:33,861 But again, the good algorithm designer should never be content, 10 00:00:33,861 --> 00:00:36,806 never be complacent. Should always ask can we do better? 11 00:00:36,806 --> 00:00:42,815 Maybe we do even better than M Log N. Well, believe it or not, you can do 12 00:00:42,815 --> 00:00:45,707 better than these implementations. At least in principle, 13 00:00:45,707 --> 00:00:48,599 at least, in theory. You have to work pretty hard and I'm 14 00:00:48,599 --> 00:00:52,266 definitely not going to discuss the algorithms or the analysis that prove 15 00:00:52,266 --> 00:00:54,487 this fact. But let me just mention a couple 16 00:00:54,487 --> 00:00:58,670 references that give MST algorithms with asymptotic run times even better than M 17 00:00:58,670 --> 00:01:01,570 Log N. So quite shockingly, if you're happy with 18 00:01:01,570 --> 00:01:05,522 randomized algorithms, as we were with say, the quit sort sorting algorithm. 19 00:01:05,522 --> 00:01:09,422 Then the minimum cost spanning tree problem can be solved in linear time. 20 00:01:09,422 --> 00:01:13,535 That's obviously an optimal algorithm. You have to look at the whole graph to 21 00:01:13,535 --> 00:01:17,755 compute the minimum cost spanning tree. But you can solve the problem in time a 22 00:01:17,755 --> 00:01:21,300 constant factor, larger than what it takes to read the input. 23 00:01:21,300 --> 00:01:25,331 This algorithm is much, much newer than Prim and Kruskal's algorithm, as you 24 00:01:25,331 --> 00:01:28,341 might expect. It does date back to the 20th century, 25 00:01:28,341 --> 00:01:30,975 but definitely the latter stages of last century. 26 00:01:30,975 --> 00:01:35,061 So the names of a couple of the inventors of this algorithm will already be 27 00:01:35,061 --> 00:01:38,447 familiar to those of you that paid close attention in part one. 28 00:01:38,447 --> 00:01:42,264 so the Carver here is the same as the author of the randomized and cut 29 00:01:42,264 --> 00:01:46,349 algorithm you studied in part one. Tarjan's name is coming up a couple times 30 00:01:46,349 --> 00:01:50,488 in these courses, but for example when we discuss strongly connected component 31 00:01:50,488 --> 00:01:53,194 algorithms. So, what if you're not happy with the 32 00:01:53,194 --> 00:01:56,189 bound just on the bound just on the expected running time, with the 33 00:01:56,189 --> 00:01:58,379 expectation over the coin flips of the algorithm? 34 00:01:58,379 --> 00:02:00,391 What if you wanted a deterministic algorithm? 35 00:02:00,391 --> 00:02:03,609 So, if we think of this randomized algorithm as being analogous to quick 36 00:02:03,609 --> 00:02:06,604 sort in the sorting problem, what would be the analog of merge sort? 37 00:02:06,604 --> 00:02:10,323 Well, it turns out we do not know whether or not there is a linear time 38 00:02:10,323 --> 00:02:13,335 deterministic algorithm for minimum spanning trees, 39 00:02:13,335 --> 00:02:17,055 that's an open question. You might think, here at this, late date, 40 00:02:17,055 --> 00:02:21,721 2012, 2013 we'd know everything there is to know about minimum cost spanning 41 00:02:21,721 --> 00:02:24,437 trees. We do not know, if there exists a linear 42 00:02:24,437 --> 00:02:28,512 time deterministic algorithm. We do know that there's a deterministic 43 00:02:28,512 --> 00:02:32,340 algorithm, with a running time, absurdly close to linear. 44 00:02:32,340 --> 00:02:36,876 Specifically, there's an algorithm with running time M, 45 00:02:36,876 --> 00:02:42,084 the number of edges times alpha of N. So what, you ask, is alpha of N? 46 00:02:42,084 --> 00:02:47,208 What is this function? Well, it's something called the inverse 47 00:02:47,208 --> 00:02:50,529 Ackermann function. So, defining the Ackermann function and 48 00:02:50,529 --> 00:02:52,815 its inverse actually takes a little bit of work. 49 00:02:52,815 --> 00:02:56,197 So I'm not going to do it right now. For those of you that are curious, you 50 00:02:56,197 --> 00:02:59,626 should check out the optional material on the union find data structure. 51 00:02:59,626 --> 00:03:03,484 Which is yet another context where sort of unbelievably, this inverse Ackermann 52 00:03:03,484 --> 00:03:06,008 function arises. But for the present context, what you 53 00:03:06,008 --> 00:03:09,287 should is Is that this is a crazy slow growing function. 54 00:03:09,287 --> 00:03:12,642 It's not constant. For any number C, I can exhibit a large 55 00:03:12,642 --> 00:03:16,292 enough value of N, so that this function values is lease C. 56 00:03:16,292 --> 00:03:20,412 So that alpha of N is a lease C. So, it's not bounded by a constant, 57 00:03:20,412 --> 00:03:23,768 but it's mind boggling how slow growing this function is. 58 00:03:23,768 --> 00:03:28,006 Let me actually just give you an incredibly slow growing function which 59 00:03:28,006 --> 00:03:32,126 actually goes much faster than the inverse Ackermann, just to prove the 60 00:03:32,126 --> 00:03:35,667 point. Specifically, the inverse Ackermann 61 00:03:35,667 --> 00:03:38,335 function grows quite a bit slower than log star N. 62 00:03:38,335 --> 00:03:42,444 Log star N I can define for you easily. We recall our definition of log base two, 63 00:03:42,444 --> 00:03:46,446 way back when we first demystified logarithms at the beginning of part one. 64 00:03:46,446 --> 00:03:50,608 If you type N into your calculator, and you keep dividing by two, you count the 65 00:03:50,608 --> 00:03:53,756 number of times you divide by two until you drop below one, 66 00:03:53,756 --> 00:03:57,278 that's log based two of N. For log star, instead of dividing by two, 67 00:03:57,278 --> 00:04:00,000 you're going to hit the log button on your calculator, 68 00:04:00,000 --> 00:04:04,385 ad you count how many times you hit log, until, the result drops below one. 69 00:04:04,385 --> 00:04:08,830 That number, the number of times you hit log, is defined to be Log star of N. 70 00:04:10,050 --> 00:04:15,432 The log star function as the inverse of the function which is a tower of 2s. 71 00:04:15,432 --> 00:04:20,957 The function which takes as input you know, an integer say T and raises two to 72 00:04:20,957 --> 00:04:24,607 itself T times. So, to appreciate just how slow growing 73 00:04:24,607 --> 00:04:28,054 the log star function is, let alone the inverse Ackerman function. 74 00:04:28,054 --> 00:04:32,031 What you should do is type in the biggest number you can into your nearest 75 00:04:32,031 --> 00:04:35,424 calculator or computer. Just keep typing in nines as long as you 76 00:04:35,424 --> 00:04:37,545 can. Then go ahead and evaluate log star. 77 00:04:37,545 --> 00:04:40,196 Keep applying log function till it drops below one. 78 00:04:40,196 --> 00:04:43,855 Probably, the result's going to be something in the neighborhood of five. 79 00:04:43,855 --> 00:04:47,937 So log star of the biggest number in your calculator or computer is going to be 80 00:04:47,937 --> 00:04:50,323 five. That's how, that's how slow growing this 81 00:04:50,323 --> 00:04:54,500 function is. So, the upshot is that the algorithms 82 00:04:54,500 --> 00:04:59,360 community has the time complexity of the MST problem almost nailed, but not quite, 83 00:04:59,360 --> 00:05:03,320 in the deterministic case. The right answer is somewhere between M 84 00:05:03,320 --> 00:05:07,040 and M times inverse Ackermann function, and we don't know where. 85 00:05:07,040 --> 00:05:09,080 But, you know what? It gets weirder. 86 00:05:13,020 --> 00:05:17,180 So check out the following result of Pettie and Ramachandran. 87 00:05:17,180 --> 00:05:22,510 They in a sense solve, the deterministic minimum cost spanning tree problem by 88 00:05:22,510 --> 00:05:26,799 exhibiting, an algorithm, who's time complexity is optimal. So they gave an 89 00:05:26,799 --> 00:05:31,018 algorithm and they gave a proof, just in the spirit of what we did for sorting. 90 00:05:31,018 --> 00:05:35,452 They gave a proof that no algorithm could have running time asymptotically better 91 00:05:35,452 --> 00:05:39,400 than theirs. But what they didn't do, is explicitly evaluate what the time 92 00:05:39,400 --> 00:05:43,132 complexity of their algorithm is. So they managed to prove optimality, 93 00:05:43,132 --> 00:05:46,377 without actually evaluating exactly what's its running time. 94 00:05:46,377 --> 00:05:50,054 So it's certainly somewhere between linear and linear times inverse 95 00:05:50,054 --> 00:05:52,758 Ackermannn. We know that's the true time complexity 96 00:05:52,758 --> 00:05:56,003 of the problem. We know an algorithm that achieves an 97 00:05:56,003 --> 00:05:59,845 optimal complexity. But to this day we do not know what that 98 00:05:59,845 --> 00:06:05,200 optimal time complexity actually is, as a function of the graph size. 99 00:06:05,200 --> 00:06:09,217 So those are some of the most advanced things that we do know, about the minimum 100 00:06:09,217 --> 00:06:12,531 cost spanning tree problem. Let me just mention a couple of things 101 00:06:12,531 --> 00:06:16,526 that we still, to this day, do not know. So let me start with the randomized 102 00:06:16,526 --> 00:06:18,802 algorithms. Now, maybe you're reaction is, there's no 103 00:06:18,802 --> 00:06:21,927 open questions in the randomized algorithms world, because we know you 104 00:06:21,927 --> 00:06:25,140 need linear time to solve the problem. And I've told you that there is a 105 00:06:25,140 --> 00:06:28,017 randomized algorithm with expected running time that is linear. 106 00:06:28,017 --> 00:06:31,685 So what more could you want? Well, what I want is I want an algorithm 107 00:06:31,685 --> 00:06:35,676 that's not just linear time but also simple enough that I can teach it to 108 00:06:35,676 --> 00:06:38,534 other people. So ideally, it would be another graduate 109 00:06:38,534 --> 00:06:42,741 course like this. But I was actually very happy to have a randomized algorithm, 110 00:06:42,741 --> 00:06:45,762 linear time, simple enough to cover in a graduate course. 111 00:06:45,762 --> 00:06:49,052 The current linear time algorithms do not have that property. 112 00:06:49,052 --> 00:06:52,720 They're more complicated than I can even cover in a graduate course. 113 00:06:52,720 --> 00:06:56,965 To accomplish this task, it turns out to be enough to solve a seemingly simpler 114 00:06:56,965 --> 00:07:00,888 task, namely, to get a simple randomized linear time algorithm for the MST 115 00:07:00,888 --> 00:07:03,897 verification problem. So let me tell you what that means. 116 00:07:03,897 --> 00:07:07,874 So in a MST problem you're supposed to optimize amongst all exponentially 117 00:07:07,874 --> 00:07:11,044 minimum spanning trees. You got to find me the one with the 118 00:07:11,044 --> 00:07:14,269 smallest sum of edge cost. In MST verification, the job seems 119 00:07:14,269 --> 00:07:16,472 simpler. I'm actually going to hand you, a 120 00:07:16,472 --> 00:07:19,609 candidate MST or I'm going to hand you a spanning tree. 121 00:07:19,609 --> 00:07:24,199 It may or may not be the best one and you just need to check, is it the optimal one 122 00:07:24,199 --> 00:07:26,743 or not. Furthermore, in the event that it's not 123 00:07:26,743 --> 00:07:30,448 optimal you should tell me edges that are not in the spanning tree. 124 00:07:30,448 --> 00:07:33,380 Edges that are too expensive that I should throw out. 125 00:07:35,240 --> 00:07:40,104 The reason it's enough to design a linear time algorithm for this seemingly simpler 126 00:07:40,104 --> 00:07:43,924 problem, is that the content of the Karger-Klein-Tarjan paper, is a 127 00:07:43,924 --> 00:07:46,717 reduction. A randomized reduction from optimizing 128 00:07:46,717 --> 00:07:50,880 over spanning trees, to the seemingly simpler problem of MST verification. 129 00:07:50,880 --> 00:07:54,472 Moreover, all of the novel content in the Karger-Klein-Tarjan algorithm. 130 00:07:54,472 --> 00:07:57,722 It's linear time, it's randomized, and it is really simple. 131 00:07:57,722 --> 00:08:00,915 I teach this stuff in that paper in my graduate classes. 132 00:08:00,915 --> 00:08:04,393 But it needs this MST verification subroutine as a black box. 133 00:08:04,393 --> 00:08:09,011 And the only known implementations that are linear time for MST verification are 134 00:08:09,011 --> 00:08:11,805 quite complicated. So, find a simple way to do MST 135 00:08:11,805 --> 00:08:16,195 verification that runs in linear time. And you're good to go with your simple 136 00:08:16,195 --> 00:08:19,567 optimal MST algorithm. For deterministic algorithms, the holy 137 00:08:19,567 --> 00:08:22,408 grail is obvious. We'd love to have a deterministic 138 00:08:22,408 --> 00:08:24,804 algorithm for MST that runs in linear time. 139 00:08:24,804 --> 00:08:28,927 Or at the very least, we just need to figure out, you know, what is the best 140 00:08:28,927 --> 00:08:32,270 possible time complexity of any deterministic MST algorithm. 141 00:08:32,270 --> 00:08:35,690 So one of the takeaways of this discussion is that, you know? 142 00:08:35,690 --> 00:08:40,366 For all the amazing advances by computer scientists on the design and analysis of 143 00:08:40,366 --> 00:08:44,699 algorithms over the past 50 years or so. There are still totally fundamental 144 00:08:44,699 --> 00:08:49,032 things that we do not understand. So there's still great ideas to come in 145 00:08:49,032 --> 00:08:51,474 the future. So if you've been intrigued by some of 146 00:08:51,474 --> 00:08:55,057 the things that I've said in this video. And you want to learn more about these 147 00:08:55,057 --> 00:08:57,244 advanced minimum cost spanning tree algorithms. 148 00:08:57,244 --> 00:09:00,874 For further reading, I'd recommend a survey by Jason Eisner, called State of 149 00:09:00,874 --> 00:09:04,317 the Art Minimum Spanning Tree Algorithms. It's about fifteen years old now. 150 00:09:04,317 --> 00:09:08,040 But it's still an amazing resource for learning about this advanced material.