Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:wendy:chapter4 [2011/03/01 00:45] – shangw
+++ courses:cs211:winter2011:journals:wendy:chapter4 [2011/03/01 14:55] – [Section 7: Clustering] shangw
@@ Line 77: / Line 77: @@
 ===== Section 7: Clustering =====
-This section talks about another problem-Clustering-and how to solve it with greedy algorithm. Clustering (of maximum spacing) can be precisely described as
+This section talks about another problem-Clustering-and how to solve it with greedy algorithm. Clustering (of maximum spacing) can be precisely described as partitioning a collection of objects U such that the maximum possible spacing s achieved (That is, the minimum distance between any pair of points lying in different clusters is minimized).
+The algorithm is exactly the Kruskal's algorithm except that we stop it just before adding the last k-1th edge, hence its running time is O(mlogn). Basically, it is constructing the minimum spanning tree without the k-1 most weighted edges. We can prove it using a contradiction.
+Practical applications can be finding out the clusters and using low-cost network within the cluster and using more robust network between each cluster.
+This section is quite short but the application of the minimum spanning tree is interesting.