Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionvi [2012/03/01 03:43] – [A simple Data Structure for Union-Find] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionvi [2012/03/01 03:54] (current) – [Implementing Kruskal's Algorithm] mugabej
@@ Line 35: / Line 35: @@
 ==== A simple Data Structure  for Union-Find ====
-  * Maintain an Array ** Component ** of size n that contains the name of the set currently containing each element
+>>>>>>>>>>>>>>>>> Maintain an Array ** Component ** of size n that contains the name of the set currently containing each element\\
-  * Let S = {1,...,n}
+>>>>>>>>>>>>>>>>> Let S = {1,...,n}\\
-  * Component[s] = the name of set containing s
+>>>>>>>>>>>>>>>>> Component[s] = the name of set containing s\\
-  * To implement ** MakeUnionFind(S) **:
+>>>>>>>>>>>>>>>>> To implement ** MakeUnionFind(S) **:\\
-    * Set up an array and initialize it to Component[s] = s for all s in S
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Set up an array and initialize it to Component[s] = s for all s in S\\
-    * With this operation, Find(v) is done in O(1) time
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> With this operation, Find(v) is done in O(1) time\\
-    * But Union(A,B) can take O(n) time with this operation(-->We have to update the values of Component[s] for all elements in A and B)
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> But Union(A,B) can take O(n) time with this operation(-->We have to update the values of Component[s] for all elements in A and B)\\
-    * To improve on this bound of Union(A,B):
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> To improve on this bound of Union(A,B):\\
-      * Maintain the list of elements in each set
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Maintain the list of elements in each set\\
-      * Choose the name for the union to be the name of one of the sets, so we only update Component[s] for s in the other set
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Choose the name for the union to be the name of one of the sets, so we only update Component[s] for s in the other set\\
-      * If the other set is big, name the union to be the name of that set and update Component[s] for s in the smaller set
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If the other set is big, name the union to be the name of that set and update Component[s] for s in the smaller set\\
-      * Maintain an Array Size of length n
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Improvements:\\
-      * Size[A] = the size of A
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Maintain an Array Size of length n\\
-      * So when a Union(A,B) operation is needed, we use the name of the larger set for the union and update Component for only the smaller set
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Size[A] = the size of A\\
-      * However, we still have a O(n) time even after the improvements
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> So when a Union(A,B) operation is needed, we use the name of the larger set for the union and update Component for only the smaller set\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> However, we still have a O(n) time even after the improvements\\
-    * So, overall, Find(u) takes O(1) time,MakeUnionFind(A,B) takes O(n) time and any sequence of k Union operations takes at most O(klogk) time
+>>>>>>>>>>>>>>>>> So, overall, Find(u) takes O(1) time,MakeUnionFind(A,B) takes O(n) time and any sequence of k Union operations takes at most O(klogk) time with this simple implementation of the algorithm.\\
 \\
 ==== A Better Implementation for Union-Find ====
@@ Line 64: / Line 65: @@
 >>>>>>>>>>>>>>>>> Find(u) takes O(logn) time \\
+==== Implementing Kruskal's Algorithm ====
+>>>>>>>>>>>>>>>>> T = {}
+>>>>>>>>>>>>>>>>> foreach (u ∈ V) make a set containing singleton u
+>>>>>>>>>>>>>>>>> for i = 1 to m
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (u,v) = ei
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if (u and v are in different sets)
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> T = T ∪ {ei}
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> merge the sets containing u and v
+>>>>>>>>>>>>>>>>> return T
+( The above algorithm, is from the class discussion)
+\\
+\\
+Kruskal's algorithm implemented as above runs in O(mlogn) time.
+\\
+\\
+This section was also interesting, although it contained some long proofs. I give it an 8/10