The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

439 ratings

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 2

Kruskal's MST algorithm and applications to clustering; advanced union-find (optional).

- Tim RoughgardenProfessor

Computer Science

In this optional video, I'm going to give you a glimpse of the research frontier on

Â the problem of computing Minimum Cost, Spanning Trees.

Â We've now seen two excellent algorithms for this problem.

Â Prim's algorithm and Kruskal's algorithm. And we had suitable data structures both

Â running near linear time. Big O of M Log N, where M is the number

Â of edges, N is the number of vertices.

Â Now going ahead we should be pretty happy with those algorithms.

Â We're only a log factor slower than what it takes to read the input.

Â But again, the good algorithm designer should never be content,

Â never be complacent. Should always ask can we do better?

Â Maybe we do even better than M Log N. Well, believe it or not, you can do

Â better than these implementations. At least in principle,

Â at least, in theory. You have to work pretty hard and I'm

Â definitely not going to discuss the algorithms or the analysis that prove

Â this fact. But let me just mention a couple

Â references that give MST algorithms with asymptotic run times even better than M

Â Log N. So quite shockingly, if you're happy with

Â randomized algorithms, as we were with say, the quit sort sorting algorithm.

Â Then the minimum cost spanning tree problem can be solved in linear time.

Â That's obviously an optimal algorithm. You have to look at the whole graph to

Â compute the minimum cost spanning tree. But you can solve the problem in time a

Â constant factor, larger than what it takes to read the input.

Â This algorithm is much, much newer than Prim and Kruskal's algorithm, as you

Â might expect. It does date back to the 20th century,

Â but definitely the latter stages of last century.

Â So the names of a couple of the inventors of this algorithm will already be

Â familiar to those of you that paid close attention in part one.

Â so the Carver here is the same as the author of the randomized and cut

Â algorithm you studied in part one. Tarjan's name is coming up a couple times

Â in these courses, but for example when we discuss strongly connected component

Â algorithms. So, what if you're not happy with the

Â bound just on the bound just on the expected running time, with the

Â expectation over the coin flips of the algorithm?

Â What if you wanted a deterministic algorithm?

Â So, if we think of this randomized algorithm as being analogous to quick

Â sort in the sorting problem, what would be the analog of merge sort?

Â Well, it turns out we do not know whether or not there is a linear time

Â deterministic algorithm for minimum spanning trees,

Â that's an open question. You might think, here at this, late date,

Â 2012, 2013 we'd know everything there is to know about minimum cost spanning

Â trees. We do not know, if there exists a linear

Â time deterministic algorithm. We do know that there's a deterministic

Â algorithm, with a running time, absurdly close to linear.

Â Specifically, there's an algorithm with running time M,

Â the number of edges times alpha of N. So what, you ask, is alpha of N?

Â What is this function? Well, it's something called the inverse

Â Ackermann function. So, defining the Ackermann function and

Â its inverse actually takes a little bit of work.

Â So I'm not going to do it right now. For those of you that are curious, you

Â should check out the optional material on the union find data structure.

Â Which is yet another context where sort of unbelievably, this inverse Ackermann

Â function arises. But for the present context, what you

Â should is Is that this is a crazy slow growing function.

Â It's not constant. For any number C, I can exhibit a large

Â enough value of N, so that this function values is lease C.

Â So that alpha of N is a lease C. So, it's not bounded by a constant,

Â but it's mind boggling how slow growing this function is.

Â Let me actually just give you an incredibly slow growing function which

Â actually goes much faster than the inverse Ackermann, just to prove the

Â point. Specifically, the inverse Ackermann

Â function grows quite a bit slower than log star N.

Â Log star N I can define for you easily. We recall our definition of log base two,

Â way back when we first demystified logarithms at the beginning of part one.

Â If you type N into your calculator, and you keep dividing by two, you count the

Â number of times you divide by two until you drop below one,

Â that's log based two of N. For log star, instead of dividing by two,

Â you're going to hit the log button on your calculator,

Â ad you count how many times you hit log, until, the result drops below one.

Â That number, the number of times you hit log, is defined to be Log star of N.

Â The log star function as the inverse of the function which is a tower of 2s.

Â The function which takes as input you know, an integer say T and raises two to

Â itself T times. So, to appreciate just how slow growing

Â the log star function is, let alone the inverse Ackerman function.

Â What you should do is type in the biggest number you can into your nearest

Â calculator or computer. Just keep typing in nines as long as you

Â can. Then go ahead and evaluate log star.

Â Keep applying log function till it drops below one.

Â Probably, the result's going to be something in the neighborhood of five.

Â So log star of the biggest number in your calculator or computer is going to be

Â five. That's how, that's how slow growing this

Â function is. So, the upshot is that the algorithms

Â community has the time complexity of the MST problem almost nailed, but not quite,

Â in the deterministic case. The right answer is somewhere between M

Â and M times inverse Ackermann function, and we don't know where.

Â But, you know what? It gets weirder.

Â So check out the following result of Pettie and Ramachandran.

Â They in a sense solve, the deterministic minimum cost spanning tree problem by

Â exhibiting, an algorithm, who's time complexity is optimal. So they gave an

Â algorithm and they gave a proof, just in the spirit of what we did for sorting.

Â They gave a proof that no algorithm could have running time asymptotically better

Â than theirs. But what they didn't do, is explicitly evaluate what the time

Â complexity of their algorithm is. So they managed to prove optimality,

Â without actually evaluating exactly what's its running time.

Â So it's certainly somewhere between linear and linear times inverse

Â Ackermannn. We know that's the true time complexity

Â of the problem. We know an algorithm that achieves an

Â optimal complexity. But to this day we do not know what that

Â optimal time complexity actually is, as a function of the graph size.

Â So those are some of the most advanced things that we do know, about the minimum

Â cost spanning tree problem. Let me just mention a couple of things

Â that we still, to this day, do not know. So let me start with the randomized

Â algorithms. Now, maybe you're reaction is, there's no

Â open questions in the randomized algorithms world, because we know you

Â need linear time to solve the problem. And I've told you that there is a

Â randomized algorithm with expected running time that is linear.

Â So what more could you want? Well, what I want is I want an algorithm

Â that's not just linear time but also simple enough that I can teach it to

Â other people. So ideally, it would be another graduate

Â course like this. But I was actually very happy to have a randomized algorithm,

Â linear time, simple enough to cover in a graduate course.

Â The current linear time algorithms do not have that property.

Â They're more complicated than I can even cover in a graduate course.

Â To accomplish this task, it turns out to be enough to solve a seemingly simpler

Â task, namely, to get a simple randomized linear time algorithm for the MST

Â verification problem. So let me tell you what that means.

Â So in a MST problem you're supposed to optimize amongst all exponentially

Â minimum spanning trees. You got to find me the one with the

Â smallest sum of edge cost. In MST verification, the job seems

Â simpler. I'm actually going to hand you, a

Â candidate MST or I'm going to hand you a spanning tree.

Â It may or may not be the best one and you just need to check, is it the optimal one

Â or not. Furthermore, in the event that it's not

Â optimal you should tell me edges that are not in the spanning tree.

Â Edges that are too expensive that I should throw out.

Â The reason it's enough to design a linear time algorithm for this seemingly simpler

Â problem, is that the content of the Karger-Klein-Tarjan paper, is a

Â reduction. A randomized reduction from optimizing

Â over spanning trees, to the seemingly simpler problem of MST verification.

Â Moreover, all of the novel content in the Karger-Klein-Tarjan algorithm.

Â It's linear time, it's randomized, and it is really simple.

Â I teach this stuff in that paper in my graduate classes.

Â But it needs this MST verification subroutine as a black box.

Â And the only known implementations that are linear time for MST verification are

Â quite complicated. So, find a simple way to do MST

Â verification that runs in linear time. And you're good to go with your simple

Â optimal MST algorithm. For deterministic algorithms, the holy

Â grail is obvious. We'd love to have a deterministic

Â algorithm for MST that runs in linear time.

Â Or at the very least, we just need to figure out, you know, what is the best

Â possible time complexity of any deterministic MST algorithm.

Â So one of the takeaways of this discussion is that, you know?

Â For all the amazing advances by computer scientists on the design and analysis of

Â algorithms over the past 50 years or so. There are still totally fundamental

Â things that we do not understand. So there's still great ideas to come in

Â the future. So if you've been intrigued by some of

Â the things that I've said in this video. And you want to learn more about these

Â advanced minimum cost spanning tree algorithms.

Â For further reading, I'd recommend a survey by Jason Eisner, called State of

Â the Art Minimum Spanning Tree Algorithms. It's about fifteen years old now.

Â But it's still an amazing resource for learning about this advanced material.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.