User:Sorting-searching-TADM2O - Revision history

Matt: Matt moved page User:Sorting-searching-TADM2E to User:Sorting-searching-TADM2O over redirect

2020-07-23T14:19:01Z

2020-07-23T14:17:55Z

2020-07-23T14:15:13Z

Attempted to restore the most recent legitimate version of the page.

2020-07-20T00:18:55Z

2020-07-18T19:49:13Z

2020-07-14T01:43:54Z

Replaced content with "TaTaatatatattataa"

2020-06-19T17:38:17Z

Adding link on task solution

2019-02-24T02:24:10Z

Fixed question wording to match book

2017-01-23T12:23:25Z

2016-09-22T21:49:15Z

‎Sorting and Searching

← Older revision		Revision as of 19:49, 18 July 2020
Line 1:		Line 1:
−	~~TaTaatatatattataa~~	+	We will apply Quick Sort algorithm for this problem. The algorithm would be changed a bit for this specific problem by adding one step of comparing the distance between the number and the pivot whenever the number is compared for partitioning. This will be explained in the detail below.
		+
		+	First step:
		+	Pick a pivot! (recommendation median-of-three)
		+
		+	Second step:
		+	We will compare all other numbers with pivot for partitioning. After comparing, we will calculate the distance between the number and the pivot and keep the smallest distance. Then, partitioning the list into 2 parts as the normal quicksort.
		+
		+	Third step:
		+	Recursive call for each side after partitioning.
		+
		+	Note:
		+	After partitioning, the number in left side, for example, does not need to compare with the one in the right side of the pivot because the distance would definitely be larger than the distance between that number and the pivot. So the problem will be reduced by half (average case).
		+
		+	----
		+	Anther solution is we can sort the list by a fast algorithm such as merge sort which will take O(nlogn) then find the smallest distance by iterate through the sorted list which will take O(n) (this is question d)

@@ Line 216: / Line 216: @@
 and separates them from the blue.
 The second pass is just separates the elements within the red/white sub-array.
 <br>4-19.

@@ Line 114: / Line 114: @@
 The output should be an array of distinct
 elements that form the union of the sets, such that
-they appear more than once in the union.
+they appear exactly once in the union.
 #Assume that <math>A</math> and <math>B</math> are unsorted. Give an <math>O(n \log n)</math> algorithm for the problem.
 #Assume that <math>A</math> and <math>B</math> are sorted. Give an <math>O(n)</math> algorithm for the problem.

@@ Line 370: / Line 370: @@
 Give an <math>O(\lg n)</math> algorithm to find an integer <math>\leq m</math> that is not present in <math>a</math>.
 For full credit, find the smallest such integer.
 <br>4-35.

← Older revision	Revision as of 14:19, 23 July 2020
(No difference)

← Older revision	Revision as of 14:17, 23 July 2020
(No difference)

← Older revision	Revision as of 00:18, 20 July 2020
(No difference)