TADM2E 2.49 - Revision history

Matt: Undo revision 1094 by FuckMatt (talk)

2020-08-01T00:45:08Z

Undo revision 1094 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:17:09Z

Redirected page to UNTV

Matt: Undo revision 1010 by MattWars (talk)

2020-07-28T09:57:50Z

Undo revision 1010 by MattWars (talk)

MattWars at 07:12, 28 July 2020

2020-07-28T07:12:56Z

Tpourjalali at 05:42, 1 May 2020

2020-05-01T05:42:40Z

Brandon.arnold at 18:34, 13 November 2016

2016-11-13T18:34:22Z

Brandon.arnold at 18:18, 13 November 2016

2016-11-13T18:18:31Z

Brandon.arnold: /* Previous answer */

2016-11-13T18:09:53Z

‎Previous answer

Letientai299 at 12:33, 17 October 2016

2016-10-17T12:33:06Z

Algowikiadmin: Recovering wiki

2014-09-11T18:23:07Z

Recovering wiki

← Older revision		Revision as of 00:45, 1 August 2020
Line 1:		Line 1:
−	~~#REDIRECT [[UNTV]]~~	+	Some incorrect answers were reached. These have been moved to the discussion, with explanation of where the argument goes wrong.
		+
		+	The correct answer: Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:
		+
		+	<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>
		+
		+	Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. <math>n=3</math> where our formula indicates there are three different possible merges):
		+
		+	<pre>
		+	{a,b,c} -> {ab, c} -> {abc}
		+	-> {a, bc} -> {abc}
		+	-> {ac, b} -> {abc}
		+	</pre>
		+
		+	And, since we have three paths we can say that's three merges -- this counts a merge step as the same if it results in the same set of companies going on to the next stage. But, instead if we count the actual merge operations:
		+
		+	<pre>
		+	{a, b, c} -> {a+b, c}, {(a+b) + c}, {a, b+c}, {a + (b+c)},
		+	{a+c, b}, {(a+c) + b}
		+	</pre>
		+
		+	then we need to change the denominator in our previous formula:
		+
		+	<math>2^{n-1} \rightarrow 2^{n-2}</math> to get six steps.
		+
		+	__________________________________________________________________________________
		+
		+	Solution above is correct given its assumptions but this problem can be more interesting. According to the examples above, {a, b, c, d} -> {ab, c, d} -> {ab, cd} is different from {a, b, c, d} -> {a, b, cd} -> {ab, cd}. I would argue that the two paths are the same. I would define two path to be the same if each employee of each company sees their own company merging sequentially with the same companies in both paths. In the example above, the employees of company c see that they merged with d and then with ab in both paths to full merger. Think about this. It is kinda complicated. So if we write down an individual merge sequence for each of the companies, then two paths are equal if all of their individual merge sequences are equal. Now how to calculate the number of paths?
		+
		+	Pick company number N and assume it's IBM. Now consider IBM's individual merging path. It could be {IBM} -> {IBM, DELL}, or {IBM} -> {IBM, DELL, Apple} or {IBM} -> {IBM, Google, Netflix, Amazon}. The aspect I'm emphasizing here is that in its first merger, IBM could merge with 1 to n-1 many companies. We can compute all of the paths by adding up these scenarios. So let's say IBM will be merging with i companies in its first merger. How many paths would we have now. Let's define f(n) to be the number of merger paths for n companies (the number we are trying to find). Then there are <math> {n-1 \choose i} </math> ways to pick the i companies IBM will be merging with. Those companies have to merge only with each other before they merge with IBM and there are f(i) ways to do that. After IBM has merge with the i companies, then we have n-i companies left to merge (counting the big set of i companies as one company), and there are f(n-i) ways to do that. So we get the recursive equation: <math> f(n) = \sum^{n-1}_{i=1} f(i)f(n-i){n-1 \choose i} </math>.

← Older revision		Revision as of 10:17, 31 July 2020
Line 1:		Line 1:
−	~~Some incorrect answers were reached. These have been moved to the discussion, with explanation of where the argument goes wrong.~~	+	#REDIRECT [[UNTV]]
−
−	The correct answer: Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:
−
−	~~<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>~~
−
−	Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. <math>n=3</math> where our formula indicates there are three different possible merges):
−
−	~~<pre>~~
−	~~{a,b,c} -> {ab, c} -> {abc}~~
−	~~-> {a, bc} -> {abc}~~
−	~~-> {ac, b} -> {abc}~~
−	~~</pre>~~
−
−	And, since we have three paths we can say that's three merges -- this counts a merge step as the same if it results in the same set of companies going on to the next stage. But, instead if we count the actual merge operations:
−
−	~~<pre>~~
−	~~{a, b, c} -> {a+b, c}, {(a+b) + c}, {a, b+c}, {a + (b+c)},~~
−	~~{a+c, b}, {(a+c) + b}~~
−	~~</pre>~~
−
−	~~then we need to change the denominator in our previous formula:~~
−
−	~~<math>2^{n-1} \rightarrow 2^{n-2}</math> to get six steps.~~
−
−	~~__________________________________________________________________________________~~
−
−	Solution above is correct given its assumptions but this problem can be more interesting. According to the examples above, {a, b, c, d} -> {ab, c, d} -> {ab, cd} is different from {a, b, c, d} -> {a, b, cd} -> {ab, cd}. I would argue that the two paths are the same. I would define two path to be the same if each employee of each company sees their own company merging sequentially with the same companies in both paths. In the example above, the employees of company c see that they merged with d and then with ab in both paths to full merger. Think about this. It is kinda complicated. So if we write down an individual merge sequence for each of the companies, then two paths are equal if all of their individual merge sequences are equal. Now how to calculate the number of paths?
−
−	Pick company number N and assume it's IBM. Now consider IBM's individual merging path. It could be {IBM} -> {IBM, DELL}, or {IBM} -> {IBM, DELL, Apple} or {IBM} -> {IBM, Google, Netflix, Amazon}. The aspect I'm emphasizing here is that in its first merger, IBM could merge with 1 to n-1 many companies. We can compute all of the paths by adding up these scenarios. So let's say IBM will be merging with i companies in its first merger. How many paths would we have now. Let's define f(n) to be the number of merger paths for n companies (the number we are trying to find). Then there are <math> {n-1 \choose i} </math> ways to pick the i companies IBM will be merging with. Those companies have to merge only with each other before they merge with IBM and there are f(i) ways to do that. After IBM has merge with the i companies, then we have n-i companies left to merge (counting the big set of i companies as one company), and there are f(n-i) ways to do that. So we get the recursive equation: <math> f(n) = \sum^{n-1}_{i=1} f(i)f(n-i){n-1 \choose i} </math>.

@@ Line 3: / Line 3: @@
 The correct answer: Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:
-<math>\prod_{i=3}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>
+<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>
 Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. <math>n=3</math> where our formula indicates there are three different possible merges):

@@ Line 3: / Line 3: @@
 The correct answer: Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:
-<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>
+<math>\prod_{i=3}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>
 Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. <math>n=3</math> where our formula indicates there are three different possible merges):

← Older revision		Revision as of 05:42, 1 May 2020
Line 23:		Line 23:

	<math>2^{n-1} \rightarrow 2^{n-2}</math> to get six steps.		<math>2^{n-1} \rightarrow 2^{n-2}</math> to get six steps.
		+
		+	__________________________________________________________________________________
		+
		+	Solution above is correct given its assumptions but this problem can be more interesting. According to the examples above, {a, b, c, d} -> {ab, c, d} -> {ab, cd} is different from {a, b, c, d} -> {a, b, cd} -> {ab, cd}. I would argue that the two paths are the same. I would define two path to be the same if each employee of each company sees their own company merging sequentially with the same companies in both paths. In the example above, the employees of company c see that they merged with d and then with ab in both paths to full merger. Think about this. It is kinda complicated. So if we write down an individual merge sequence for each of the companies, then two paths are equal if all of their individual merge sequences are equal. Now how to calculate the number of paths?
		+
		+	Pick company number N and assume it's IBM. Now consider IBM's individual merging path. It could be {IBM} -> {IBM, DELL}, or {IBM} -> {IBM, DELL, Apple} or {IBM} -> {IBM, Google, Netflix, Amazon}. The aspect I'm emphasizing here is that in its first merger, IBM could merge with 1 to n-1 many companies. We can compute all of the paths by adding up these scenarios. So let's say IBM will be merging with i companies in its first merger. How many paths would we have now. Let's define f(n) to be the number of merger paths for n companies (the number we are trying to find). Then there are <math> {n-1 \choose i} </math> ways to pick the i companies IBM will be merging with. Those companies have to merge only with each other before they merge with IBM and there are f(i) ways to do that. After IBM has merge with the i companies, then we have n-i companies left to merge (counting the big set of i companies as one company), and there are f(n-i) ways to do that. So we get the recursive equation: <math> f(n) = \sum^{n-1}_{i=1} f(i)f(n-i){n-1 \choose i} </math>.

← Older revision		Revision as of 18:34, 13 November 2016
Line 1:		Line 1:
−	Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:	+	Some incorrect answers were reached. These have been moved to the discussion, with explanation of where the argument goes wrong.
		+
		+	The correct answer: Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:

	<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>		<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>

← Older revision		Revision as of 18:18, 13 November 2016
Line 1:		Line 1:
−	~~Let's <math>f(n)</math> denotes the number of ways <math>n</math> company can~~
−	~~merge. We have (assume that ''merge'' in this problem doesn't mean ''acquire''~~
−	~~as the later is not commutative)~~
−
−	~~- <math>f(2) = 1</math>.~~
−	~~- <math>f(3) = 3</math>. From 3 companies, we can first merge any 2 to reduce the size of set to 2. Then, we can merge the 2 new companies. There're 3 ways to select 2 companies from 3.~~
−	- <math>f(n) = \binom{n}{n-1}f(n-1)</math>. We can merge <math>n</math> companies by first merge <math>n-1</math> ones of them, and then merge the last 2 remaining companies. There're <math>\binom{n}{n-1} = n</math> ways to select a sub set of <math>n-1</math> items from <math>n</math> items. And we already know that there're <math>f(n-1)</math> ways to merge the subset (with <math>n \ge 3</math>.
−
−	~~So, our final function is:~~
−
−	~~<math>~~
−	~~f(n) = n.f(n-1) = n(n-1)(n-2)\ldots 3 = \frac{n!}{2}~~
−	~~</math>~~
−
−
−	~~'''Note''': my answer is different with the old answer by another wiki editor.~~
−	~~I don't know if my understanding about the problems is correct. It's up to the~~
−	~~next editor to justify and edit this page again.~~
−
−	~~My argument is the old solution has some duplication in the way the companies~~
−	~~merge together, while my solution is not. Consider <math>n=4</math>.~~
−
−	~~The old solution first select 2 companies to merge, reduce the size of set from~~
−	~~4 to 3, and then select 2 companies in new set to merge. So, some thing like~~
−	~~the following might happen:~~
−
−	~~<pre>~~
−	~~{a,b,c,d}~~
−	~~-> {ab, c, d}, {a, b, cd}~~
−	~~-> {ab, cd} and {ab, cd} // This is a duplication, thus, the result is invalid.~~
−	~~</pre>~~
−
−	~~Meanwhile, my solution first try to combine <math>n-1</math> companies. And because all subset is different with each other, there's no duplication appear.~~
−
−
−
	Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:		Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:

← Older revision		Revision as of 18:09, 13 November 2016
Line 34:		Line 34:


−	~~=== Previous answer ===~~
−	~~With 2 companies {a,b}, there's only one way to merge: [ab]~~

−	With three companies {a,b,c}, we need to find the number of ways that the three companies can become two companies, and for every one of those possibilities, the two remaining companies can be reduced to one in only 1 way (because we've already solved the case of two companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b}, {bc,a}], or 3.
−
−	Now we see a pattern emerging. For n companies, the answer is <math>f(n - 1) * g(n)</math>, where g(n) is the number of ways to reduce n companies to n - 1 companies. g(n) is the sum from 1 to n - 1 of n, which is <math>n(n - 1)/2</math>. Thus, the answer is <math>f(n - 1) * n(n - 1)/2</math>.
−
−	~~'''Another answer:'''~~
	Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:		Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:

← Older revision		Revision as of 12:33, 17 October 2016
Line 1:		Line 1:
		+	Let's <math>f(n)</math> denotes the number of ways <math>n</math> company can
		+	merge. We have (assume that ''merge'' in this problem doesn't mean ''acquire''
		+	as the later is not commutative)
		+
		+	- <math>f(2) = 1</math>.
		+	- <math>f(3) = 3</math>. From 3 companies, we can first merge any 2 to reduce the size of set to 2. Then, we can merge the 2 new companies. There're 3 ways to select 2 companies from 3.
		+	- <math>f(n) = \binom{n}{n-1}f(n-1)</math>. We can merge <math>n</math> companies by first merge <math>n-1</math> ones of them, and then merge the last 2 remaining companies. There're <math>\binom{n}{n-1} = n</math> ways to select a sub set of <math>n-1</math> items from <math>n</math> items. And we already know that there're <math>f(n-1)</math> ways to merge the subset (with <math>n \ge 3</math>.
		+
		+	So, our final function is:
		+
		+	<math>
		+	f(n) = n.f(n-1) = n(n-1)(n-2)\ldots 3 = \frac{n!}{2}
		+	</math>
		+
		+
		+	'''Note''': my answer is different with the old answer by another wiki editor.
		+	I don't know if my understanding about the problems is correct. It's up to the
		+	next editor to justify and edit this page again.
		+
		+	My argument is the old solution has some duplication in the way the companies
		+	merge together, while my solution is not. Consider <math>n=4</math>.
		+
		+	The old solution first select 2 companies to merge, reduce the size of set from
		+	4 to 3, and then select 2 companies in new set to merge. So, some thing like
		+	the following might happen:
		+
		+	<pre>
		+	{a,b,c,d}
		+	-> {ab, c, d}, {a, b, cd}
		+	-> {ab, cd} and {ab, cd} // This is a duplication, thus, the result is invalid.
		+	</pre>
		+
		+	Meanwhile, my solution first try to combine <math>n-1</math> companies. And because all subset is different with each other, there's no duplication appear.
		+
		+
		+	=== Previous answer ===
	With 2 companies {a,b}, there's only one way to merge: [ab]		With 2 companies {a,b}, there's only one way to merge: [ab]

@@ Line 3: / Line 3: @@
 With three companies {a,b,c}, we need to find the number of ways that the three companies can become two companies, and for every one of those possibilities, the two remaining companies can be reduced to one in only 1 way (because we've already solved the case of two companies).  In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b}, {bc,a}], or 3.
-Now we see a pattern emerging.  For n companies, the answer is &lt;math&gt;f(n - 1) * g(n)&lt;/math&gt;, where g(n) is the number of ways to reduce n companies to n - 1 companies.  g(n) is the sum from 1 to n - 1 of n, which is &lt;math&gt;n(n - 1)/2&lt;/math&gt;.  Thus, the answer is &lt;math&gt;f(n - 1) * n(n - 1)/2&lt;/math&gt;.
+Now we see a pattern emerging.  For n companies, the answer is <math>f(n - 1) * g(n)</math>, where g(n) is the number of ways to reduce n companies to n - 1 companies.  g(n) is the sum from 1 to n - 1 of n, which is <math>n(n - 1)/2</math>.  Thus, the answer is <math>f(n - 1) * n(n - 1)/2</math>.
 '''Another answer:'''
-Assuming pairwise merges (no k-way merges) we have &lt;math&gt;n-1&lt;/math&gt; merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have &lt;math&gt;\binom{n}{2}&lt;/math&gt; ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:
+Assuming pairwise merges (no k-way merges) we have <math>n-1</math> merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have <math>\binom{n}{2}</math> ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:
-&lt;math&gt;\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}&lt;/math&gt;
+<math>\prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}}</math>
-Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. &lt;math&gt;n=3&lt;/math&gt; where our formula indicates there are three different possible merges):
+Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. <math>n=3</math> where our formula indicates there are three different possible merges):
-&lt;pre&gt;
+<pre>
-{a,b,c} -&gt; {ab, c} -&gt; {abc}
+{a,b,c} -> {ab, c} -> {abc}
-         -&gt; {a, bc} -&gt; {abc}
+         -> {a, bc} -> {abc}
-         -&gt; {ac, b} -&gt; {abc}
+         -> {ac, b} -> {abc}
-&lt;/pre&gt;
+</pre>
 And, since we have three paths we can say that's three merges -- this counts a merge step as the same if it results in the same set of companies going on to the next stage. But, instead if we count the actual merge operations:
-&lt;pre&gt;
+<pre>
-{a, b, c} -&gt; {a+b, c}, {(a+b) + c}, {a, b+c}, {a + (b+c)},
+{a, b, c} -> {a+b, c}, {(a+b) + c}, {a, b+c}, {a + (b+c)},
               {a+c, b}, {(a+c) + b}
-&lt;/pre&gt;
+</pre>
 then we need to change the denominator in our previous formula:
-&lt;math&gt;2^{n-1} \rightarrow 2^{n-2}&lt;/math&gt; to get six steps.
+<math>2^{n-1} \rightarrow 2^{n-2}</math> to get six steps.