Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter4 [2011/02/28 23:43] – shangw
+++ courses:cs211:winter2011:journals:wendy:chapter4 [2011/03/01 14:55] – [Section 7: Clustering] shangw
@@ Line 61: / Line 61: @@
 The readability is 7.
+===== Section 6: The Implementing Kruskal's Algorithm: the Union-Find Data Structure =====
+The main goal of this section is to introduce the Union-Find data structure, which will allow us to quickly find if two nodes are connected, which is exactly needed in the Kruskal's Algorithm, because we always want to check if the nodes connected by an edge is connected by another path.
+There are three operations in the data structure, namely MakeUnionFind,Find and Union. MakeUnionFind(S) separates each element in S to be an individual set. Find(u) finds out which set u is contained. Union(S1,S2) merges two sets together. From this, we can see that Union-Find data structure is handy when we hope to combine sets, but definitely not split a set in a desired way other than individual element as a set.
+If we use an array to implement the Union-Find, we use the location of each element of the array to represent each node and fill in the number to represent the set the node belongs in. Therefore, we can easily see that the running time for Find is O(1), and MakeUnionFind(S) O(n). Any sequence of k Union operations takes at most O(klogk). Because at most 2k elements are involved in any Union at all and the process happens at most log2(2k) times.
+There is actually a better data structure than arrays to implement Union-Find, especially for the Union operation. The key is using a pointer. MakeUnionFind(S) does similar things as above and has each set pointing to the element inside. When union two sets, we simply have the smaller set's pointer points at the larger set's pointer. Obviously, MakeUinonFind takes O(n) time and Union constant time. The Find(v) ultimately does is try to find what element is the set containing v points to. Since the set containing has at least 1 elements, at most n, and its size doubles most logn time, the running time is O(logn).
+We can even further improve the algorithm to make Find(v) constant. However, setting up the data structure takes over more time, because we need to go though the pointing path for each element in the sets as we did in the Find above.
+After looking into the data structure, it is not hard to implement Kruskal's Algorithm in O(mlogn) time.
+This section talks in details of the construction of Union-Find, interesting. The readability is 9.
+===== 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 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.