This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.
MST Context
Loading...
From the course by Princeton University
Algorithms, Part II
421 ratings
From the lesson
Minimum Spanning Trees
In this lecture we study the minimum spanning tree problem. We begin by considering a generic greedy algorithm for the problem. Next, we consider and implement two classic algorithm for the problem—Kruskal's algorithm and Prim's algorithm. We conclude with some applications and open problems.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
So we're going to complete our study of MST algorithms by considering some context
both as an unsolved problem in theoretical computer science and as a practical
problem. So the unsolved problem in theoretical
computer science that has defied researchers for many decades is, it is
possible to find a linear-time MST algorithm?
Is there an algorithm that only examines each edge at most once on the average?
Now, this doesn't have. That much practical comp.
Consequence since the versions of Primm's algorithm that we've talked about can get
the running time down quite low for the sparse graphs, the huge sparse graphs that
we encounter in practice. But it's still, its...
Like union find, it's a tantalizing problem.
Unlike union find, it hasn't been resolved yet.
Union find remember, we couldn't get a linear algorithm but at least Tarjan
proved that no such algorithm exists. For MST, we're not even there yet.
And a lot of people have worked on it. So let's go with the simple model where
what you get to do is compare edges. Compare weights on edges.
In 1975 Yao proved that there exists an algorithm that's worst case running time
is e log, log v. In 1976, Cheriton and Tarjan came up with
another such algorithm. And then Fredman and Tarjan found the e
plus e log v algorithm or e log star v For MST's in'84.
Here's another one. E log, log star v.
Now remember, log star v is the number of times you take log to get to one.
So it's, less than, six, in the natural universe.
So these are very, very close to linear algorithms.
The names in orange are people who work at Princeton.
So, we're now trumpeting Princeton a little bit here.
In'97, Chazelle showed that, its close to the, inverse Ackerman function.
That, even more slowly growing than log star v.
In 2000, got rid of the log factor, so very, very close to linear.
That now. In 2002, Optimal, well, let's, talk about
that. They, they, they showed an, an algorithm
that it, better not to talk about the theory of that.
[laugh]. And that the, still, the open question is,
is there, an algorithm whose worst case running time is guaranteed to be
proportional to e? Or could, someone prove that no such
algorithm exists? It's one of the most, tantalizing open
questions in computer science. As we get into, graph algorithms in more
detail. We'll see some other examples of problems
for which we know pretty good algorithms but would like to know whether there are
better algorithms or not. And MST is a fine example of that.
That's the orange means Princeton. There is a randomized linear time
algorithm that was discovered in 1995, but that's not the same as solving it worst
case in linear time. So that's one context.
Mxt is an important problem that's still been studied by theoretical computer
scientist and we still don't know the best algorithm.
Here's another one, So-called Euclidean MST.
And this one is what's appropriate in some practical situations.
So now you have points in the plane and the graph is an implicit dense graph.
That is, we take as an edge in the graph, the distance between this point and every
other point. So if there's n points there's n squared
edges because every point's connected to every other point.
And what we want is, in that graph, we want to find the subset of edges that
connects all the points, that's minimal. That's actually, in a lot of practical
problems, that's what you want. So as it stands, the algorithms that we've
talked about are not useful for this beacause they're going to take quadratic
time, because e's quadratic. That's how many edges there are in the
graph. So you know, you could just go ahead and
build the graph with the N squared over two distances and run Prim's algorithm.
But that's not very satisfying for a huge number of points.
It's actually not Too difficult to exploit the geometry of
the situation. And get it done in time proportional to N
log N. What is typically done is to build a sub
graph, where each point is connected to a certain number of points that are close to
it. There's a particular graph called the
Voronoi diagram, or the Delaunay triangulation, that does that.
And it's been proved, number one that, that graph has linear number of edges not,
quadratic, and it's also the MST is a sub graph of the d-linear triangulation.
So you can get it done in linear arrhythmic time for Euclidean MST.
Separate problem related but still a very interesting in many practical
applications. Here's another application in se, several
scientific studies, there's the idea of clustering.
And so what we wanna do is, we have a set of objects and they're related by a
distance function that specifies how close they are and what we wanna do is divide
the objects into a given number k of coherent groups so that objects in
different clusters are far apart. So wanna see how things cluster together.
And here's a really old example of a application of this where there was an
outbook, outbreak of cholera deaths in. London in the 1850s and, if you plot where
all of the deaths happened, scientific study could find that they were clustered
around certain places. And, actually they were able to identify
well pumps that were leading to the, the cholera just by doing clustering study.
And, that is a very special case. There are many, many other applications
where clustering is an important process, an important thing to be able to compute.
So like mobile networks for web search there's an idea of the distance between
doc, documents and you wanna categorize them in clusters.
There's the, all the objects that have been discovered in the sky, you wanna
cluster them together in a reasonable way. And all kinds of. Of processing having to
do with huge data bases, trying to get information that seems close together to
be close together into a relatively small number of clusters.
So there's, a, a approach called single link clustering.
Where you talk about the single length, the distance between two clusters equaling
the distance between the two closest objects, one in each cluster.
And so, so-called single length clustering is given at integer K.
Find the K clustering that maximizes the distance between the two closest clusters.
So that's a well defined computational problem.
And there's a very well-known algorithm, in the science literature for this
problem, signal, signal-link clustering. Form of e-clusters, find the closest pair
of objects such that each object's in a different cluster, and merge the two
clusters. And repeat until they're exactly
k-clusters. You'll find this algorithm in the
scientific literature. What's amazing is that, this is
Crussical's algorithm, just stop when you found the k-connected components, so that,
the, Or another thing you could do is just run Prim's algorithm and then after you've
run Prim's algorithm get rid of the largest edges until you're left with
k-clusters. So out of all the efficient Algorithms
that we've talked about are gonna apply for single-link clustering.
And actually scientists who also know some computer science now are able to handle
huge problems that would not be possible without efficient algorithms.
This is just one, one example where a, a cancer study where experiments are
connecting genes with the way they're expressed in different parts of the body,
and trying to cluster together tumors in similar tissues.
And again, such experimental results can amount, result in huge amounts of data,
and MST algorithms are playing a role in scientific research of this type.
That's our context for minimal spanning trees.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
