Union-Find - Revision history

Savoundg at 08:30, 16 October 2016

2016-10-16T08:30:58Z

← Older revision		Revision as of 08:30, 16 October 2016
Line 159:		Line 159:
	* Find the ''successor'' of ''x'': the smallest ''y'' in such that ''y >= x''.		* Find the ''successor'' of ''x'': the smallest ''y'' in such that ''y >= x''.
	design a data type so that all operations (except construction) should take logarithmic time or better.		design a data type so that all operations (except construction) should take logarithmic time or better.

			== References ==
			{\| class="wikitable"
			\|Case Study: Union-Find
			\|http://algs4.cs.princeton.edu/15uf/
			\|}

Savoundg: /* Interview Questions */

2016-10-13T21:50:07Z

Interview Questions

← Older revision		Revision as of 21:50, 13 October 2016
Line 144:		Line 144:

	= Interview Questions =		= Interview Questions =
			From the textbook ''Algorithms, 4th Edition'' by Robert Sedgewick and Kevin Wayne.

	=== Social network connectivity ===		=== Social network connectivity ===

Savoundg: /* Interview Questions */

2016-10-13T21:45:44Z

Interview Questions

← Older revision		Revision as of 21:45, 13 October 2016
Line 145:		Line 145:
	= Interview Questions =		= Interview Questions =

	=== ~~'''~~Social network connectivity~~'''~~ ===		=== Social network connectivity ===
	Given a social network containing ''n'' members and a log file containing ''m'' timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be ''m log n'' or better and use extra space proportional to ''n''.		Given a social network containing ''n'' members and a log file containing ''m'' timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be ''m log n'' or better and use extra space proportional to ''n''.

	=== ~~'''~~Union-find with specific canonical element~~'''~~ ===		=== Union-find with specific canonical element ===
	Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing ''i''. The operations, union(), connected(), and find() should all take logarithmic time or better.		Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing ''i''. The operations, union(), connected(), and find() should all take logarithmic time or better.

	For example, if one of the connected components is {1, 2, 6, 9} , then the find() method should return for each of the four elements in the connected components.		For example, if one of the connected components is {1, 2, 6, 9} , then the find() method should return for each of the four elements in the connected components.

	=== ~~'''~~Successor with delete~~'''~~ ===		=== Successor with delete ===
	Given a set of integers ''S = {0, 1, ..., N-1}'' and a sequence of requests of the following form:		Given a set of integers ''S = {0, 1, ..., N-1}'' and a sequence of requests of the following form:
	* Remove ''x'' from ''S''		* Remove ''x'' from ''S''
	* Find the ''successor'' of ''x'': the smallest ''y'' in such that ''y >= x''.		* Find the ''successor'' of ''x'': the smallest ''y'' in such that ''y >= x''.
	design a data type so that all operations (except construction) should take logarithmic time or better.		design a data type so that all operations (except construction) should take logarithmic time or better.

Savoundg at 21:44, 13 October 2016

2016-10-13T21:44:26Z

← Older revision		Revision as of 21:44, 13 October 2016
Line 142:		Line 142:
	\|N + M lg* N		\|N + M lg* N
	\|}		\|}

			= Interview Questions =

			=== '''Social network connectivity''' ===
			Given a social network containing ''n'' members and a log file containing ''m'' timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be ''m log n'' or better and use extra space proportional to ''n''.

			=== '''Union-find with specific canonical element''' ===
			Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing ''i''. The operations, union(), connected(), and find() should all take logarithmic time or better.

			For example, if one of the connected components is {1, 2, 6, 9} , then the find() method should return for each of the four elements in the connected components.

			=== '''Successor with delete''' ===
			Given a set of integers ''S = {0, 1, ..., N-1}'' and a sequence of requests of the following form:
			* Remove ''x'' from ''S''
			* Find the ''successor'' of ''x'': the smallest ''y'' in such that ''y >= x''.
			design a data type so that all operations (except construction) should take logarithmic time or better.

Savoundg at 21:16, 13 October 2016

2016-10-13T21:16:23Z

@@ Line 63: / Line 63: @@
 Maintain an additional array to keep track of the number of elements in the given tree.
 * Find: same as Quick-Union
-* Union: Link root of smaller tree to root of larger tree
+* Union: Link root of smaller tree to root of larger tree<syntaxhighlight lang="java">
 == Comparison ==
@@ Line 71: / Line 115: @@
 !Find
 !Union
 |-
 |Quick-Find
@@ Line 76: / Line 122: @@
 |1
 |N
 |-
 |Quick-Union
@@ Line 81: / Line 128: @@
 |N
 |N
 |-
 |Weighted Quick-Union
+|
+|
 |}

Savoundg at 16:21, 13 October 2016

2016-10-13T16:21:51Z

← Older revision		Revision as of 16:21, 13 October 2016
Line 7:		Line 7:
	How to merge two sub-set of elements efficiently?		How to merge two sub-set of elements efficiently?

	=== Quick-Find (eager approach) ===		== Quick-Find (eager approach) ==
	Integer array of size N.		Integer array of size N.

Line 27:		Line 27:
	</syntaxhighlight>		</syntaxhighlight>

	Quick-Find Union is too slow!		Quick-Find '''Union''' is too slow!

	=== Quick-Union (lazy approach) ===		== Quick-Union (lazy approach) ==
	Same data structure as Quick-Find but the interpretation is different: id[i] is the parent of i.		Same data structure as Quick-Find but the interpretation is different: id[i] is the parent of i.

Line 54:		Line 54:
	id[root(p)] = root(q);		id[root(p)] = root(q);
	}		}
	</syntaxhighlight>Quick-Union Find is too slow!		</syntaxhighlight>Quick-Union '''Find''' is too slow!

	=== ~~Weighted~~ Quick-Union ===		== Weighted Quick-Union ==
			Modify Quick-Union union to avoid tall tree by tracking the size of each tree.

			The smaller tree goes below the other tree when merging.

			Maintain an additional array to keep track of the number of elements in the given tree.
			* Find: same as Quick-Union
			* Union: Link root of smaller tree to root of larger tree

			== Comparison ==
	{\| class="wikitable"		{\| class="wikitable"
	!Algorithm		!Algorithm
Line 73:		Line 82:
	\|N		\|N
	\|-		\|-
			\|Weighted Quick-Union
	\|		\|
	\|		\|N
	\|
	\|		\|
	\|}		\|}

Savoundg: /* Weighting */

2016-10-12T19:56:06Z

Weighting

← Older revision		Revision as of 19:56, 12 October 2016
Line 56:		Line 56:
	</syntaxhighlight>Quick-Union Find is too slow!		</syntaxhighlight>Quick-Union Find is too slow!

	=== ~~Weighting~~ ===		=== Weighted Quick-Union ===
	{\| class="wikitable"		{\| class="wikitable"
	!Algorithm		!Algorithm

Savoundg at 19:28, 12 October 2016

2016-10-12T19:28:36Z

← Older revision		Revision as of 19:28, 12 October 2016
Line 12:		Line 12:
	Interpretation: p and q are connected iff they have the same id: id[p]=id[q]		Interpretation: p and q are connected iff they have the same id: id[p]=id[q]
	* Find: If id[p] = id[q], p and q are connected		* Find: If id[p] = id[q], p and q are connected
	* Union: put them in the same sub-set: replace all id[p~~] value by~~ id[q]		* Union: put them in the same sub-set: replace all sub-set id of p to the sub-set id of q
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	boolean connected(int p, int q)		boolean connected(int p, int q)
	{		{
	return id[p] == id[q];		return id[p] == id[q];
	}		}

	void union(int p, int q)		void union(int p, int q)
	{		{
	for (int i = 0; i < N; i++)		for (int i = 0; i < N; i++)
	if (id[i] == id[q])		if (id[i] == id[q])
	id[i] = id[p];		id[i] = id[p];
	}		}
	</syntaxhighlight>		</syntaxhighlight>

	Quick-Find is too slow!		Quick-Find Union is too slow!

	=== Quick-Union (lazy approach) ===		=== Quick-Union (lazy approach) ===
	Same data structure as Quick-Find but the interpretation is different: id[i] is parent of i.		Same data structure as Quick-Find but the interpretation is different: id[i] is the parent of i.

	The p is a root if id[p]=id[id[p]].		The p is a root if id[p]=id[id[p]].
	* Find: If root(p) = root(q), p and q are connected		* Find: If root(p) = root(q), p and q are connected
	* Union: root(p) := root(q)		* Union: change root of p to root of q<syntaxhighlight lang="java">
			int root(int p)
			{
			int root = p;

			while (root != id[root])
			root = id[root);

			return root;
			}

			boolean connected(int p, int q)
			{
			root(p) == root(q);
			}

			void union(int p, int q)
			{
			id[root(p)] = root(q);
			}
			</syntaxhighlight>Quick-Union Find is too slow!

			=== Weighting ===
	{\| class="wikitable"		{\| class="wikitable"
	!Algorithm		!Algorithm
Line 47:		Line 69:
	\|-		\|-
	\|Quick-Union		\|Quick-Union
	\|		\|N
	\|		\|N
	\|1		\|N
	\|-		\|-
	\|		\|

Savoundg: Elaborate on quick-find/quick-union

2016-10-12T19:14:45Z

Elaborate on quick-find/quick-union

← Older revision		Revision as of 19:14, 12 October 2016
Line 4:		Line 4:

	How to find if two elements are "connected"?		How to find if two elements are "connected"?

			How to merge two sub-set of elements efficiently?

			=== Quick-Find (eager approach) ===
			Integer array of size N.

			Interpretation: p and q are connected iff they have the same id: id[p]=id[q]
			* Find: If id[p] = id[q], p and q are connected
			* Union: put them in the same sub-set: replace all id[p] value by id[q]
			<syntaxhighlight lang="java">
			boolean connected(int p, int q)
			{
			return id[p] == id[q];
			}

			void union(int p, int q)
			{
			for (int i = 0; i < N; i++)
			if (id[i] == id[q])
			id[i] = id[p];
			}
			</syntaxhighlight>

			Quick-Find is too slow!

			=== Quick-Union (lazy approach) ===
			Same data structure as Quick-Find but the interpretation is different: id[i] is parent of i.

			The p is a root if id[p]=id[id[p]].
			* Find: If root(p) = root(q), p and q are connected
			* Union: root(p) := root(q)
			{\| class="wikitable"
			!Algorithm
			!Initialization
			!Find
			!Union
			\|-
			\|Quick-Find
			\|N
			\|1
			\|N
			\|-
			\|Quick-Union
			\|
			\|
			\|1
			\|-
			\|
			\|
			\|
			\|
			\|}

Savoundg: Created page with "Let a given set of N elements. Assume we can union two element of this set. How to find if two elements are "connected"?"

2016-10-11T20:44:17Z

Created page with "Let a given set of N elements. Assume we can union two element of this set. How to find if two elements are "connected"?"

New page

Let a given set of N elements.

Assume we can union two element of this set.

How to find if two elements are "connected"?