TADM2E 4.10 - Revision history

Matt: Undo revision 1170 by Matt (talk)

2020-08-02T12:11:29Z

Undo revision 1170 by Matt (talk)

Matt: Undo revision 1169 by Matt (talk)

2020-08-02T12:11:12Z

Undo revision 1169 by Matt (talk)

Matt: Undo revision 1143 by FuckyouMatt (talk)

2020-08-02T12:10:52Z

Undo revision 1143 by FuckyouMatt (talk)

FuckyouMatt: Blanked the page

2020-08-02T02:11:01Z

Blanked the page

Matt: Undo revision 1075 by FuckMatt (talk)

2020-08-01T00:54:53Z

Undo revision 1075 by FuckMatt (talk)

Matt: Undo revision 1076 by FuckMatt (talk)

2020-08-01T00:54:42Z

Undo revision 1076 by FuckMatt (talk)

FuckMatt at 09:43, 31 July 2020

2020-07-31T09:43:27Z

FuckMatt at 09:43, 31 July 2020

2020-07-31T09:43:13Z

Matt: Undo revision 1047 by FuckMatt (talk)

2020-07-30T09:33:43Z

Undo revision 1047 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-30T01:56:19Z

Blanked the page

← Older revision	Revision as of 12:11, 2 August 2020
Line 1:	Line 1:
	+	Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />
	+	For various values of k, <br />
	+	k Solution Time Complexity <br />
	+	1 O(<math>n^0logn</math>) <br />
	+	2 O(<math>n^1logn</math>) <br />
	+	3 O(<math>n^2logn</math>) <br />
	+	4 O(<math>n^3logn</math>) <br />

	+	for k = 2 onwards <br />
	+	1. sort the array ( nlogn ) <br />
	+	2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />
	+	eg: <br />
	+	for k = 3 <br />
	+	for( i = 0; i < n; i++ ) <br />
	+	for( j = i+1; j < n; j++ ) <br />
	+	# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />
	+
	+	<h3>Another recursive solution</h3>
	+	First, we note that [[ TADM2E 4.8 \| an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
	+
	+	<pre>
	+	sort S ascending;
	+	CheckSumOfK(S, k, T); // defined below
	+
	+	// S must be aorted array of integers
	+	function CheckSumOfK(S, k, T)
	+	if k <= 2:
	+	Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.
	+
	+	Initialize array A of n - 1 elements;
	+	for i from 0 to n - 1:
	+	k = 0
	+	// Collect in A all numbers in S but S[i]. Note that A will still be sorted.
	+	for j from 0 to n - 1:
	+	if i != j:
	+	A[k] = S[j];
	+	k = k + 1
	+	// If S[i] is included in the k integers that sum up to T, then there must
	+	// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).
	+	// We can find that out by calling ourselves recursively.
	+	if CheckSumOfK(A, k - 1, T - S[i]):
	+	return True
	+	return False
	+	</pre>
	+
	+	<h3>Complexity</h3>
	+	For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
	+	work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.
	+
	+	A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 \| this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
	+	item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
	+
	+	Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.

← Older revision		Revision as of 12:11, 2 August 2020
Line 1:		Line 1:
−	~~Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />~~
−	~~For various values of k, <br />~~
−	~~k Solution Time Complexity <br />~~
−	~~1 O(<math>n^0logn</math>) <br />~~
−	~~2 O(<math>n^1logn</math>) <br />~~
−	~~3 O(<math>n^2logn</math>) <br />~~
−	~~4 O(<math>n^3logn</math>) <br />~~

−	~~for k = 2 onwards <br />~~
−	~~1. sort the array ( nlogn ) <br />~~
−	~~2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />~~
−	~~eg: <br />~~
−	~~for k = 3 <br />~~
−	~~for( i = 0; i < n; i++ ) <br />~~
−	~~for( j = i+1; j < n; j++ ) <br />~~
−	~~# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />~~
−
−	~~<h3>Another recursive solution</h3>~~
−	First, we note that [[ TADM2E 4.8 \| an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
−
−	~~<pre>~~
−	~~sort S ascending;~~
−	~~CheckSumOfK(S, k, T); // defined below~~
−
−	~~// S must be aorted array of integers~~
−	~~function CheckSumOfK(S, k, T)~~
−	~~if k <= 2:~~
−	~~Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.~~
−
−	~~Initialize array A of n - 1 elements;~~
−	~~for i from 0 to n - 1:~~
−	~~k = 0~~
−	~~// Collect in A all numbers in S but S[i]. Note that A will still be sorted.~~
−	~~for j from 0 to n - 1:~~
−	~~if i != j:~~
−	~~A[k] = S[j];~~
−	~~k = k + 1~~
−	~~// If S[i] is included in the k integers that sum up to T, then there must~~
−	~~// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).~~
−	~~// We can find that out by calling ourselves recursively.~~
−	~~if CheckSumOfK(A, k - 1, T - S[i]):~~
−	~~return True~~
−	~~return False~~
−	~~</pre>~~
−
−	~~<h3>Complexity</h3>~~
−	For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
−	~~work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.~~
−
−	A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 \| this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
−	item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
−
−	Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.

← Older revision	Revision as of 12:10, 2 August 2020
Line 1:	Line 1:
	+	Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />
	+	For various values of k, <br />
	+	k Solution Time Complexity <br />
	+	1 O(<math>n^0logn</math>) <br />
	+	2 O(<math>n^1logn</math>) <br />
	+	3 O(<math>n^2logn</math>) <br />
	+	4 O(<math>n^3logn</math>) <br />

	+	for k = 2 onwards <br />
	+	1. sort the array ( nlogn ) <br />
	+	2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />
	+	eg: <br />
	+	for k = 3 <br />
	+	for( i = 0; i < n; i++ ) <br />
	+	for( j = i+1; j < n; j++ ) <br />
	+	# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />
	+
	+	<h3>Another recursive solution</h3>
	+	First, we note that [[ TADM2E 4.8 \| an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
	+
	+	<pre>
	+	sort S ascending;
	+	CheckSumOfK(S, k, T); // defined below
	+
	+	// S must be aorted array of integers
	+	function CheckSumOfK(S, k, T)
	+	if k <= 2:
	+	Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.
	+
	+	Initialize array A of n - 1 elements;
	+	for i from 0 to n - 1:
	+	k = 0
	+	// Collect in A all numbers in S but S[i]. Note that A will still be sorted.
	+	for j from 0 to n - 1:
	+	if i != j:
	+	A[k] = S[j];
	+	k = k + 1
	+	// If S[i] is included in the k integers that sum up to T, then there must
	+	// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).
	+	// We can find that out by calling ourselves recursively.
	+	if CheckSumOfK(A, k - 1, T - S[i]):
	+	return True
	+	return False
	+	</pre>
	+
	+	<h3>Complexity</h3>
	+	For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
	+	work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.
	+
	+	A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 \| this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
	+	item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
	+
	+	Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.

← Older revision		Revision as of 02:11, 2 August 2020
Line 1:		Line 1:
−	~~Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />~~
−	~~For various values of k, <br />~~
−	~~k Solution Time Complexity <br />~~
−	~~1 O(<math>n^0logn</math>) <br />~~
−	~~2 O(<math>n^1logn</math>) <br />~~
−	~~3 O(<math>n^2logn</math>) <br />~~
−	~~4 O(<math>n^3logn</math>) <br />~~

−	~~for k = 2 onwards <br />~~
−	~~1. sort the array ( nlogn ) <br />~~
−	~~2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />~~
−	~~eg: <br />~~
−	~~for k = 3 <br />~~
−	~~for( i = 0; i < n; i++ ) <br />~~
−	~~for( j = i+1; j < n; j++ ) <br />~~
−	~~# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />~~
−
−	~~<h3>Another recursive solution</h3>~~
−	First, we note that [[ TADM2E 4.8 \| an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
−
−	~~<pre>~~
−	~~sort S ascending;~~
−	~~CheckSumOfK(S, k, T); // defined below~~
−
−	~~// S must be aorted array of integers~~
−	~~function CheckSumOfK(S, k, T)~~
−	~~if k <= 2:~~
−	~~Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.~~
−
−	~~Initialize array A of n - 1 elements;~~
−	~~for i from 0 to n - 1:~~
−	~~k = 0~~
−	~~// Collect in A all numbers in S but S[i]. Note that A will still be sorted.~~
−	~~for j from 0 to n - 1:~~
−	~~if i != j:~~
−	~~A[k] = S[j];~~
−	~~k = k + 1~~
−	~~// If S[i] is included in the k integers that sum up to T, then there must~~
−	~~// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).~~
−	~~// We can find that out by calling ourselves recursively.~~
−	~~if CheckSumOfK(A, k - 1, T - S[i]):~~
−	~~return True~~
−	~~return False~~
−	~~</pre>~~
−
−	~~<h3>Complexity</h3>~~
−	For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
−	~~work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.~~
−
−	A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 \| this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
−	item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
−
−	Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.

@@ Line 6: / Line 6: @@
        O(<math>n^2logn</math>) <br />
        O(<math>n^3logn</math>) <br />
 for k = 2 onwards <br />

← Older revision	Revision as of 09:33, 30 July 2020
Line 1:	Line 1:
	+	Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />
	+	For various values of k, <br />
	+	k Solution Time Complexity <br />
	+	1 O(<math>n^0logn</math>) <br />
	+	2 O(<math>n^1logn</math>) <br />
	+	3 O(<math>n^2logn</math>) <br />
	+	4 O(<math>n^3logn</math>) <br />

	+	for k = 2 onwards <br />
	+	1. sort the array ( nlogn ) <br />
	+	2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />
	+	eg: <br />
	+	for k = 3 <br />
	+	for( i = 0; i < n; i++ ) <br />
	+	for( j = i+1; j < n; j++ ) <br />
	+	# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />
	+
	+	<h3>Another recursive solution</h3>
	+	First, we note that [[ TADM2E 4.8 \| an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
	+
	+	<pre>
	+	sort S ascending;
	+	CheckSumOfK(S, k, T); // defined below
	+
	+	// S must be aorted array of integers
	+	function CheckSumOfK(S, k, T)
	+	if k <= 2:
	+	Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.
	+
	+	Initialize array A of n - 1 elements;
	+	for i from 0 to n - 1:
	+	k = 0
	+	// Collect in A all numbers in S but S[i]. Note that A will still be sorted.
	+	for j from 0 to n - 1:
	+	if i != j:
	+	A[k] = S[j];
	+	k = k + 1
	+	// If S[i] is included in the k integers that sum up to T, then there must
	+	// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).
	+	// We can find that out by calling ourselves recursively.
	+	if CheckSumOfK(A, k - 1, T - S[i]):
	+	return True
	+	return False
	+	</pre>
	+
	+	<h3>Complexity</h3>
	+	For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
	+	work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.
	+
	+	A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 \| this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
	+	item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
	+
	+	Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.

← Older revision		Revision as of 01:56, 30 July 2020
Line 1:		Line 1:
−	~~Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br />~~
−	~~For various values of k, <br />~~
−	~~k Solution Time Complexity <br />~~
−	~~1 O(<math>n^0logn</math>) <br />~~
−	~~2 O(<math>n^1logn</math>) <br />~~
−	~~3 O(<math>n^2logn</math>) <br />~~
−	~~4 O(<math>n^3logn</math>) <br />~~

−	~~for k = 2 onwards <br />~~
−	~~1. sort the array ( nlogn ) <br />~~
−	~~2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br />~~
−	~~eg: <br />~~
−	~~for k = 3 <br />~~
−	~~for( i = 0; i < n; i++ ) <br />~~
−	~~for( j = i+1; j < n; j++ ) <br />~~
−	~~# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br />~~
−
−	~~<h3>Another recursive solution</h3>~~
−	First, we note that [[ TADM2E 4.8 \| an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:
−
−	~~<pre>~~
−	~~sort S ascending;~~
−	~~CheckSumOfK(S, k, T); // defined below~~
−
−	~~// S must be aorted array of integers~~
−	~~function CheckSumOfK(S, k, T)~~
−	~~if k <= 2:~~
−	~~Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.~~
−
−	~~Initialize array A of n - 1 elements;~~
−	~~for i from 0 to n - 1:~~
−	~~k = 0~~
−	~~// Collect in A all numbers in S but S[i]. Note that A will still be sorted.~~
−	~~for j from 0 to n - 1:~~
−	~~if i != j:~~
−	~~A[k] = S[j];~~
−	~~k = k + 1~~
−	~~// If S[i] is included in the k integers that sum up to T, then there must~~
−	~~// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).~~
−	~~// We can find that out by calling ourselves recursively.~~
−	~~if CheckSumOfK(A, k - 1, T - S[i]):~~
−	~~return True~~
−	~~return False~~
−	~~</pre>~~
−
−	~~<h3>Complexity</h3>~~
−	For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math>
−	~~work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.~~
−
−	A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 \| this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every
−	item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.
−
−	Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.