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.