TADM2E 4.2 - Revision history

Landisdesign: Clarified (d)

2019-11-20T23:57:00Z

Clarified (d)

Rdc5174 at 22:33, 14 January 2018

2018-01-14T22:33:26Z

Letientai299 at 16:50, 11 October 2016

2016-10-11T16:50:04Z

Algowikiadmin: Recovering wiki

2014-09-11T18:14:00Z

Recovering wiki

New page

(a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in O(n) worst-case time.

(b) The answer is straight forward: S[1] and S[n], since they are the two extreme values.

(c) Sort the array with any nLog(n) method. Then scan through the sorted array to find the smallest gap, thus the desired pair.

(d) Same as above.

← Older revision		Revision as of 23:57, 20 November 2019
Line 5:		Line 5:
	(c) Sort the array with any <math>n\log(n)</math> method. Then scan through the sorted array to find the smallest gap, thus the desired pair.		(c) Sort the array with any <math>n\log(n)</math> method. Then scan through the sorted array to find the smallest gap, thus the desired pair.

−	(d) Same as ~~above~~.	+	(d) Same as (c), after sorting.

← Older revision		Revision as of 22:33, 14 January 2018
Line 1:		Line 1:
−	(a) ~~Check the first 3 integers in~~ the array, ~~and get rid~~ of the ~~middle one~~. ~~Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in~~ <math>O(n)</math> worst-case time.	+	(a) Iterate over the array once, keeping track of the max and min values respectively for x and y. This will have <math>O(n)</math> worst-case time.

	(b) The answer is straight forward: <math>S[1]</math> and <math>S[n],</math> since they are the two extreme values.		(b) The answer is straight forward: <math>S[1]</math> and <math>S[n],</math> since they are the two extreme values.

@@ Line 1: / Line 1: @@
-(a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in O(n) worst-case time.
+(a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in <math>O(n)</math> worst-case time.
-(b) The answer is straight forward: S[1] and S[n], since they are the two extreme values.
+(b) The answer is straight forward: <math>S[1]</math> and <math>S[n],</math> since they are the two extreme values.
-(c) Sort the array with any nLog(n) method. Then scan through the sorted array to find the smallest gap, thus the desired pair.
+(c) Sort the array with any <math>n\log(n)</math> method. Then scan through the sorted array to find the smallest gap, thus the desired pair.
 (d) Same as above.