EECS 3101
Prof. Andy Mirzaian
STUDY MATERIAL:
• [CLRS] chapters 6, 7, 8, 9
• Lecture Notes 5, 6
2
TOPICS
The Sorting Problem
Some general facts
QuickSort
HeapSort, Heaps, Priority Queues Sorting Lower Bound
Special Purpose Sorting Algorithms The Selection Problem
Lower Bound Techniques
Prune-&-Search
3
The Sorting Problem
INPUT: A sequence A= a1 , a2 ,··· , an of n arbitrary numbers. OUTPUT: A permutation (reordering) ap(1) , ap(2) ,··· , ap(n) of the
input sequence, such that ap(1) ap(2) ··· ap(n) .
Two elementary operations:
Comparison between a pair of items ai and aj with =, <, >, or any logical combination thereof.
Exchange: swapping the positions of a pair of items ai and aj . Definition: An inversion is a pair of numbers ai , aj in the input,
such that i < j but ai > aj (i.e., the pair is out of order). I(A) = the total # of inversions in sequence A.
In general: 0 I(A) n(n-1)/2.
Example: A=4,9,4,3,6,8,2,5. I(A)=14.
a2, a7 = 9, 2 is one of the inversions in A.
4
Some Basic Facts
Swapping an adjacent pair of items will change the inversion count by +1, 0, or –1.
Any sorting algorithm that (effectively) exchanges only adjacent pairs of items is doomed to take at least W(n2) steps in the worst case.
BubbleSort, InsertionSort, SelectionSort are in this category.
MergeSort, QuickSort, HeapSort are not.
InsertionSort takes Q(n + I) time on every input, where n = # input items, and
I = # inversions in the input. Why?
This makes InsertionSort a suitable choice when the input is almost sorted (low I).
5
QUICKSORT
[C.A.R. Hoare, 1962]
History:
Hoare lived in Moscow for a period of time; first as part of the U.K. Royal Navy studying modern Russian military; then as a visiting student at Moscow State University; and later on, worked for the National Physical Lab stationed in Moscow. He collaborated with the Automatic Machine Translation of Russian to English Project Group. Dictionaries were on a long magnetic tape in alphabetical order. So they would first sort the words in a sentence, then in one pass would compare it with the magnetic tape. …
For the sorting part, he first thought of BubbleSort, but soon realized it was too slow. QuickSort was the 2nd algorithm he says he thought of.
6
Sorting Student Homework Papers
The way I sort student homework papers by name:
I first partition them into a small number of piles by initials, e.g., Pile1: A–F
Pile2: G–L Pile3: M–S Pile4: T–Z
Then I sort each pile separately, possibly first partitioning them further into more refined groups, e.g., there are many names with the same initial.
Then I reassemble the sorted piles in order.
7
Randomized QuickSort
Algorithm QuickSort(S)
Pre-Cond: input S is a finite sequence of arbitrary numbers Post-Cond: output is a permutation of S in sorted order
if |S| < 2 then return S
p a random element in S 3-Partition S into:
S< { x S : S= { x S : S> { x S :
S’< QuickSort(S<)
S’> QuickSort(S>) return S’< , S= , S’>
end
§ pivot item, why random? § we already discussed this
§ O( |S| ) time
§ Exercise Question:
§ which recursive call first?!
S< : x < p
S= :
x = p S> : x > p
x < p } x = p } x > p }
T(|S|) = T(| S< |) + T(| S> |) + Q( |S| ), T(n) = Q(1), for n=0,1.
8
QuickSort Running Time
n
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = T(i) + T(n-i-1) + Q(n), T(n) = Q(1), for n=0,1.
Worst-Case:
T(n) = maxi { T(i) + T(n-i-1) + Q(n) : i = 0 .. n –1 } = T(n – 1) + T(0) + Q(n)
= T(n – 1) + Q(n) = Q(n2)
This occurs if at all recursion levels the selected pivot is (near) the extreme;
the largest or the smallest!
9
QuickSort Running Time
n
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = T(i) + T(n-i-1) + Q(n), T(n) = Q(1), for n=0,1.
Best-Case:
T(n) = mini { T(i) + T(n-i-1) + Q(n) : i = 0 .. n –1 } = T(n/2) + T(n/2) + Q(n)
= 2T(n/2) + Q(n) = Q(n log n)
This occurs if at all recursion levels the selected pivot is (near) the median element!
10
QuickSort Running Time
n
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = T(i) + T(n-i-1) + Q(n), T(n) = Q(1), for n=0,1.
Expected-Case:
T(n) = avei { T(i) + T(n-i-1) + Q(n) : i = 0 .. n –1 }
n1
n1 T ( i ) T ( n i 1 ) Q ( n )
i0
n2 n 1 T(i) Q(n) (full history recurrence already discussed)
i0
= Q(n log n)
11
Full History Recurrence: QuickSort Example2: T(n)n2n1T(i)n, n0 [ T(0)0]
i0
1. Multiply across by n (so that we can subsequently cancel out the summation):
nT(n) 2n1 T(i)n2 , n0
i0 n2
2. Substitute n-1 for n:
(n1)T(n1) 2
nT(n) (n1)T(n1) 2T(n1) 2n1, n1
3. Subtract (2) from (1):
4. Rearrange:
i0
T(n) T(n1) 2n1 , n1
5. Divide by n(n+1) to make LHS & RHS look alike:
n1 n Q(n1) T(n1),
n(n1) 2n-1 3 1
T(i)(n1)2 , n1 nT(n) (n1)T(n1) 2n1, n1
Q(n) T(n), n1
6. Rename:
7. Simplified recurrence:
n(n1) n1 n n1 n
nth
Harmonic number
n
Q(n)Q(n1) 3 1 n1
0 forn0
8. Iteration: Q(n)3 13 1 3 1 3 1Q(0)2H(n) 3n
n1 n n n1 n1 n2 2 1 n1 9. Finally: T(n)(n1)Q(n)2(n1)H(n)3nQ(nlogn).
12
Why Randomize?
S< : x < p
i
Worst-Case: Expected-Case: Best-Case:
n
p S> : x > p
n – i –1
T(n) = Q(n2) T(n) = Q(n log n) T(n) = Q(n log n)
Randomization nullifies adverse effect of badly arranged input permutation. Algorithm sees the input as a random permutation.
Probability that almost all random choices are the worst is nearly 1/n!
FACT: Randomized QuickSort will take O(n log n) time with probability very close to 1
on every input.
(extremely low).
13
HEAPSORT,
Heaps & Priority Queues
[J.W.J. Williams, 1964]
14
Binary Heap
A = a binary tree with one key per node (duplicate keys allowed). Max Heap Order: A satisfies the following partial order:
for every node x root[A] : key[x] key[parent(x)].
Full tree node allocation scheme: nodes of A are allocated in increasing
order of level, and left-to-right within the same level.
This allows array implementation, where array indices simulate tree pointers.
91
1
84
74
23
73 81 66 54
4567
848 962 77 34 53 61 41 29
10 11 12 13
36 23 51 27 44 69 20 27 47 33 59 46
14 15
16 17 18 19 20 21 22 23 24 25 26 27
15
1
A=
Array as Binary Heap
size[A]
1
currently unused
max size
parent A[ t/2 ] node A[t]
h ≈ log n
A[2t]
left child
A[2t+1]
right child
n = size[A]
16
Some MAX Heap Properties
Root A[1] contains the maximum item.
Every root-to-leaf path appears in non-increasing order.
Every subtree is also max heap ordered. [Recursive structure]
The key at any node is the largest among all its descendants (inclusive).
(x,y) AncestorOf : A[x] A[y],
where AncestorOf = { (x,y) : node x is ancestor of node y }.
1
94
68 48 74 18 56
8 9 10 11 12
A[1]
LR
x y
2
82
45
74 76
3
92
67
68 88
17
UpHeap
A[1..n] = a max-heap.
Suddenly, item A[t] increases in value. Now A is a “t upward corrupted heap”:
(x,y) AncestorOf : y t A[x] A[y].
Question: how would you rearrange A to make it a max-heap again? Answer: percolate A[t] up its ancestral path.
procedure UpHeap(A, t) § O(log n) time Pre-Cond: A is a t upward corrupted heap
Post-Cond: A is rearranged into a max-heap
p t/2 § parent of t
if p = 0 or A[p] A[t] then return A[t] A[p]
UpHeap(A,p)
1
end t
18
UpHeap Example
1 94 2323
82 82
4 5 92 4 5 92
1 94
74 76 6 7 74 86 6 7
68 88
68 88
86
68 48 74 18 56
8 9 10 11 12
68 48 76 18 56
8
9 10 11 12
2 stop
86
1
3
45
74 82
94
92
67
68 88
68 48 76 18 56
8 9 10 11 12
19
DownHeap
A[1..n] = a max-heap.
Suddenly, item A[t] decreases in value. Now A is a “t downward corrupted heap”:
(x,y) AncestorOf : x t A[x] A[y].
Question: how would you rearrange A to make it a max-heap again? Answer: demote A[t] down along largest-child path.
procedure DownHeap(A, t) § O(log n) time Pre-Cond: A is a t downward corrupted heap
Post-Cond: A is rearranged into a max-heap c 2t § left child of t
if c > size[A] then return § c not part of heap if c < size[A] and A[c] < A[c+1] then c c+1 § now c is the largest child of t
if A[t] < A[c] then A[t] A[c] DownHeap(A, c)
t 2t 2t+1
end
20
DownHeap Example
1 94
82 76 265 92
1 94
2323
5 92 467467
74 76
68 48 74 18 56
8 9 10 11 12
68 88
74 26
68 48 74 18 56
68 88
8
9 10 11 12
1 2
76
94
45
74 74
3
92
67
68 88
68 48 26 18 56
8 9 10 11 12 stop
21
Construct Heap (or Heapify)
One application of heaps is sorting. But how do we start a heap first? Problem: Given array A[1..n], rearrange its items to form a heap.
Solution 1: Sort A[1..n] in descending order. Yes, but that’s circular! Solution 2: Build Incrementally:
That is, make A[1..t] a max heap while incrementing t 1 .. n.
That is, for t 1 .. n do
UpHeap(A, t) end
TimeQh i2i i0
1
Q(h2h )
Q(nlogn)
i
h = log n
Most nodes are concentrated near the bottom with larger depths but smaller heights. Idea: DownHeap is better!
2i
t
n
22
Heap Construction Algorithm
Solution 3: Build Backwards on t by DownHeap(A,t).
Assume items in nodes 1..t-1 are tentatively + so that DownHeap’s Pre-Cond is met.
procedure ConstructHeap(A[1..n]) § O(n) time Pre-Cond: input is array A[1..n] of arbitrary numbers Post-Cond: A is rearranged into a max-heap
size[A] n § establish last node barrier LastNonleafNode n/2
for t LastNonleafNode downto 1 do DownHeap(A, t)
end
A[1]
L
h1 TimeQ(hi)2i
i0 h
R
Qj2hj j0 h
h = log n
T(n) =
T(|L|) + T(|R|) + O(log n)
T(n) = O(n)
2h Q( j2 j ) j0
2h Q(1) Q(n)
t
2i
h-i
n
23
Construct Heap Example
1 2
23
14
3
42
4567
51 62 12 92
83 94
89
26 88 56
10 11 12
24
Construct Heap Example
2
23
3 DownHeap(A,t) 42 t=6
1
14
4567
51 62 12 92
83 94
89
26 88 56
10 11 12
25
Construct Heap Example
2
23
3 DownHeap(A,t) 42 t=5
1
14
4567
51 62 56 92
83 94
89
26 88 12
10 11 12
26
Construct Heap Example
2
23
3 DownHeap(A,t) 42 t=4
1
14
4567
51 88 56 92
83 94
89
26 62 12
10 11 12
27
Construct Heap Example
2
23
3 DownHeap(A,t) 42 t=3
1
14
4567
94 88 56 92
83 51
89
26 62 12
10 11 12
28
Construct Heap Example
2
23
3 DownHeap(A,t) 92 t=2
1
14
4567
94 88 56 42
83 51
89
26 62 12
10 11 12
29
Construct Heap Example
1
14
2
94
3
92
DownHeap(A,t) t=1
4
5
67
83 88 56
42
23
51
26 62 12
10 11 12
89
30
Construct Heap Example
MAX HEAP
1 2
88
94
3
92
4567
83 62 56 42
23 51
89
26 14 12
10 11 12
31
Heap as a Priority Queue
A Priority Queue (usually implemented with some “heap” structure)
is an abstract Data Structure that maintains a set S of items and supports the following operations on it:
MakeEmptyHeap(S): Make an empty priory queue and call it S.
ConstructHeap(S): Insert(x, S): DeleteMax(S):
Construct a priority queue containing the set S of items. Insert new item x into S (duplicate values allowed) Remove and return the maximum item from S.
Note: Min-Heap is used if we intend to do DeleteMin instead of DeleteMax.
32
Priority Queue Operations
Array A as a binary heap is a suitable implementation.
For a heap of size n, it has the following time complexities:
O(1) O(n) O(log n)
MakeEmptyHeap(A) ConstructHeap(A[1..n]) Insert(x,A) and DeleteMax(A)
size[A] 0 discussed already see below
1
procedure Insert(x,A)
size[A] size[A] + 1 A[ size[A] ] x UpHeap(A, size[A] )
end
procedure DeleteMax(A)
if size[A] = 0 then return error
MaxItem A[1] A[1] A[size[A]]
size[A] size[A] – 1 DownHeap(A, 1) return MaxItem
end
size[A]
33
A word on Priority Queues
• In many priority queue applications, an item and the priority of the item are two distinct object types.
• For instance: items are vertices in a graph, while priority of an item is the shortest distance from source to the corresponding vertex in the graph.
• We store (pointers to) items in the nodes of the heap, while item priorities are stored separately, external to the heap.
• We also maintain two-way “pointers” (node[v] and v) between items and their heap node location for direct access both ways. (node[v]=0 means v is not in the heap.)
• Heap ordering property is based not on the items but their priorities.
• The result is a priority adaptable location aware priority queue.
priority d[v]
node[v] = t
v
t
v
HEAP
v
GRAPH
34
HeapSort
Algorithm HeapSort(A[1..n]) § O(n log n) time Pre-Cond: input is array A[1..n] of arbitrary numbers
Post-Cond: A is rearranged into sorted order
ConstructMaxHeap(A[1..n]) for tn downto 2do
A[t] DeleteMax(A) end
35
HeapSort Example
(pages 36 – 68)
1 2 3 4 5 6 7 8 9 10 11 12
already constructed
94 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 56 heap swap
Max Item
1
94
68 48 74 18 56
8 9 10 11 12
size[A] = 12
2
82
45
74 76
3
92
67
68 88
36
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 94
2
82
45
74 76
1
56
3
92
67
68 88
68 48 74 18 94 8 9 10 11 12
size[A] = 12
37
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18
| 94
2
82
45
74 76
1
56
DownHeap(A,1)
3
92
67
68 88
68 48 74 18 94 8 9 10 11 12
size[A] = 11
38
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
92 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 18
| 94
Max Item
swap
1
92
size[A] = 11
2
82
45
74 76
3
88
67
68 56
68 48 74 18 94 8 9 10 11 12
39
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 92
| 94
2
82
45
74 76
1
18
3
88
67
68 56
68 48 74 92 94 8 9 10 11 12
size[A] = 11
40
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 92 | 94
2
82
45
74 76
1
18
DownHeap(A,1)
3
88
67
68 56
68 48 74 92 94 8 9 10 11 12
size[A] = 10
41
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
88 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 74 |
92 | 94
Max Item
swap
1
88
size[A] = 10
2
82
45
74 76
3
68
67
18 56
68 48 74 92 94 8 9 10 11 12
42
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 88 |
92 | 94
2
82
45
74 76
1
74
3
68
67
18 56
68 48 88 92 94 8 9 10 11 12
size[A] = 10
43
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 88 | 92 | 94
2
82
45
74 76
1
74
DownHeap(A,1)
3
68
67
18 56
68 48 88 92 94 8 9 10 11 12
size[A] =9
44
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
82 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 48 |
88 | 92 | 94
Max Item
swap
1
82
size[A] =9
2
76
45
74 74
3
68
67
18 56
68 48 88 92 94 8 9 10 11 12
45
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 82 |
88 | 92 | 94
2
76
45
74 74
1
48
3
68
67
18 56
68 82 88 92 94 8 9 10 11 12
size[A] =9
46
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 82 | 88 | 92 | 94
2
76
45
74 74
1
48
DownHeap(A,1)
3
68
67
18 56
68 82 88 92 94 8 9 10 11 12
size[A] =8
47
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
76 | 74 | 68 | 68 | 74 | 18 | 56 | 48 |
82 | 88 | 92 | 94
Max Item
swap
1
76
size[A] =8
2
74
45
68 74
3
68
67
18 56
48 82 88 92 94 8 9 10 11 12
48
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 74 | 68 | 68 | 74 | 18 | 56 | 76 |
82 | 88 | 92 | 94
2
74
45
68 74
1
48
3
68
67
18 56
76 82 88 92 94 8 9 10 11 12
size[A] =8
49
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 74 | 68 | 68 | 74 | 18 | 56 |
76 | 82 | 88 | 92 | 94
2
74
45
68 74
1
48
DownHeap(A,1)
3
68
67
18 56
76 82 88 92 94 8 9 10 11 12
size[A] =7
50
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 74 | 68 | 68 | 48 | 18 | 56 |
76 | 82 | 88 | 92 | 94
Max Item
swap
1
74
size[A] =7
2
74
45
68 48
3
68
67
18 56
76 82 88 92 94 8 9 10 11 12
51
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 74 | 68 | 68 | 48 | 18 | 74 |
76 | 82 | 88 | 92 | 94
2
74
45
68 48
1
56
3
68
67
18 74
76 82 88 92 94 8 9 10 11 12
size[A] =7
52
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 74 | 68 | 68 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94
2
74
45
68 48
1
56
DownHeap(A,1)
3
68
67
18 74
76 82 88 92 94 8 9 10 11 12
size[A] =6
53
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 68 | 68 | 56 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94 swap
Max Item
1
74
18 74 8 9 10 11 12
size[A] =6
2
68
45
3
68
67
56 48
76 82 88 92 94
54
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 68 | 68 | 56 | 48 | 74 |
74 | 76 | 82 | 88 | 92 | 94
1
18
76 82 88 92 94
8 9 10 11 12
size[A] =6
2
68
45
56 48
3
68
67
74 74
55
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 68 | 68 | 56 | 48 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
18
76 82 88 92 94
8 9 10 11 12
size[A] =5
2
68
45
56 48
DownHeap(A,1)
3
68
67
74 74
56
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
68 | 56 | 68 | 18 | 48 | 74 | 74 | 76 | 82 | 88 | 92 | 94 swap
Max Item
1
68
76 82 88 92 94
8 9 10 11 12
size[A] =5
2
56
45
18 48
3
68
67
74 74
57
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 56 | 68 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
48
76 82 88 92 94
8 9 10 11 12
size[A] =5
2
56
45
18 68
3
68
67
74 74
58
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 56 | 68 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
48
76 82 88 92 94
8 9 10 11 12
size[A] =4
2
56
45
18 68
DownHeap(A,1)
3
68
67
74 74
59
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
68 | 56 | 48 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94 swap
Max Item
1
68
76 82 88 92 94
8 9 10 11 12
size[A] =4
2
56
45
18 68
3
48
67
74 74
60
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 56 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
18
76 82 88 92 94
8 9 10 11 12
size[A] =4
2
56
45
68 68
3
48
67
74 74
61
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 56 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
18
76 82 88 92 94
8 9 10 11 12
size[A] =3
2
56
45
68 68
DownHeap(A,1)
3
48
67
74 74
62
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 18 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
Max Item
swap
2
18
45
68 68
76 82 88 92 94
8 9 10 11 12
1
56
size[A] =3
3
48
67
74 74
63
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 18 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
48
76 82 88 92 94
8 9 10 11 12
size[A] =3
2
18
45
68 68
3
56
67
74 74
64
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 18 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
48
76 82 88 92 94
8 9 10 11 12
size[A] =2
2
18
45
68 68
DownHeap(A,1)
3
56
67
74 74
65
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 18 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
Max Item
swap
2
18
45
68 68
76 82 88 92 94
8 9 10 11 12
1
48
size[A] =2
3
56
67
74 74
66
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 48 |
56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
1
18
76 82 88 92 94
8 9 10 11 12
size[A] =2
2
48
45
68 68
3
56
67
74 74
67
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 48 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
size[A] =1
SORTED ARRAY
45
68 68
76 82 88 92 94
8 9 10 11 12
2
48
1
18
3
56
67
74 74
68
SORTING LOWER BOUND
My friend, it’s impossible for one person to build this ship in one month, using only wood, saw, hammer and nail!
69
n Black Boxes
Box 1
Box 2 Box 3
The adversary shows you 3 black boxes.
Each contains a distinct number.
Your task is to order these boxes in increasing order of the numbers they contain. You are not allowed to open the boxes or examine their contents in any way.
You can only ask the oracle questions of the type:
“Is the number in Box x < the number in Box y?” ( “x : y” for short)
where x and y are in {1, 2, 3} and completely your choice.
In the worst case, how many questions of this type do you need to ask?
Below is a possible scenario called the decision tree of the strategy you might use:
< 1 :2 >
< 2 :3 > < 2 :3
1,2,3
1 :3 1 :3 <><>
1,3,2 3,1,2 2,1,3 2,3,1
>
3,2,1
70
The Decision Tree Model
General Sorting: no assumption on item type.
We only know there is a linear ordering defined on the items.
Comparison types: =, < , > (or any question with binary (yes/no) answer) Relative ordering information is gained by comparing pairs of items.
For simplicity first assume all input items are distinct.
n! possible permutations of input items a1 , a2 ,··· , an
Sn = set of all n! permutations.
S = set of possible outcomes at node x. Comp (ai : aj) at node x.
max{|S’|,|S”|} 1⁄2|S| <
Sn S
ai : aj
x
>
S’ = subset of S
consistent with
S” = subset of S
consistent with
ai < aj
ai > aj 71
Information Theory Lower Bound on Sorting
Sn S
ai : aj
x
<
>
S’ = subset of S
consistent with
ai < aj
S” = subset of S
consistent with
ai > aj
log ( max { |S’| , |S”| } ) log (|S|) – 1
log n!
Sorting Lower Bound:
length of worst path down the decision tree is
log n!
W(n log n)
log 1 = 0
72
worst-path down
Information Theory Lower Bound
L leaves
# of possible outcomes
L 2H
In a 3-way decision tree, it’s log base 3.
height H
Worst- case # of comparisons H log (# possible outcomes).
73
More Decision Tree Lower Bounds
FACT 0: Any comparison based sorting algorithm requires at least W(n log n) comparisons in the worst-case.
FACT 1: Any comparison based sorting algorithm requires at least W(n log n) comparisons even in the average-case.
Proof: #LeavesinT = mT =mL + mR .
Average leaf depth = Sum of leaf depths / # leaves. Proof by induction that
Sum of leaf depths (#leaves) log (# leaves). Basis (one leaf): Trivial.
Induction: Sum of leaf depths in T
T:
LR
mL leaves mR leaves mT leaves
mT n!
(by Induction Hypothesis) (m log m is convex:
min at mL= mR = 1⁄2 mT) 74
= =
=
=
=
S{ depth(x, T) : x is a
S{ depth(x, T) : x is a + S{ depth(x, T) : x is a
S{ 1 + depth(x, L) : x + S{ 1 + depth(x, R) : x
mT + S{ depth(x, L) : + S{ depth(x, R) :
leaf in T} leaf in L} leaf in R}
is a leaf in L} is a leaf in R} x is a leaf in L}
x is a leaf in R} mT + mL log mL + mR log mR
mT + (1⁄2 mT)log(1⁄2 mT) + (1⁄2 mT)log(1⁄2 mT) mT log mT
FACT 0: FACT 1: FACT 2:
More Decision Tree Lower Bounds
Any comparison based sorting algorithm requires at least W(n log n) comparisons in the worst-case.
Any comparison based sorting algorithm requires at least W(n log n) comparisons even in the average-case.
Any comparison based Merging algorithm of two sorted lists, each with n elements, requires at least W(n) comparisons in the worst-case.
Proof: There are 2n output elements. How many possible outcomes?
The outcome is uniquely determined by the n output spots that the elements of the first list occupy.
How many possibilities are there to pick n spots out of 2n spots?
n! n!
Use eq. (3.18): approximation formula for n!, on page 57 of [CLRS]
2n (2n)!
Answer: # outcomes = n
log (# outcomes) = log (2n)! – 2 log n! 2n – 1⁄2 log n W(n).
75
Algebraic Decision Tree
Suppose we want to sort n real numbers.
Why should our computation be restricted to only element comparisons?
What about something like:
Is (3a1 + 6a2)*(7a5 – 6a9) – 15 a3*a4 – 8 < 0 ?
Michael Ben Or [1983], using an earlier result of [Petrovskiĭ, Oleĭnik, Thom, Milnor], addressed that concern by developing
the more powerful Algebraic Computation Tree Model.
In this tree model, internal nodes can be of two types:
a computation node: it does arithmetic op’s on input items & constants.
a decision node: it asks whether a computed quantity is =0, or <0, or >0.
He showed that (even if we assume the cost of computation nodes are
free of charge) there must be paths with many decision type nodes.
For instance, he showed the following result:
FACT 3: Sorting requires at least W(n log n) comparisons in the worst-case, even in the Algebraic Computation Tree Model.
76
Ben Or’s Lower Bound Method
A sequence x1 , x2 ,··· , xn of n real numbers can be interpreted as a point in n, the n dimensional real space.
Similarly, for any permutation p of 1,2, …, n, xp(1) , xp(2) ,··· , xp(n) is a point in that space.
Permutation xp(1) , xp(2) ,··· , xp(n) is the sorted order if and only if the input point x1 , x2 ,··· , xn falls in the following subset of the space:
S(p) = { x1 , x2 ,··· , xn : xp(i) xp(i+1) , for i = 1 .. n-1}.
The entire n dimensional space is partitioned into such regions.
Each algebraic expression computed in the model is sign invariant in a
subset of n.
The intersection of these subsets must fall within a unique S(p) as a
certificate that p is the correct sorted permutation of the input.
The lower bound argument is that we need many such intersections to
achieve the goal.
77
More Algebraic Computation Tree Lower Bounds
FACT: The following problems have worst-case W(n log n) lower bounds in the Algebraic Computation Tree Model.
Element Uniqueness:
Are any two elements of the input sequence x1 , x2 ,··· , xn equal? Set Intersection:
Giventwosets{x1 ,x2 ,···, xn} and{y1 ,y2 ,···, yn},dotheyintersect?
Set Equality:
Giventwosets{x1 ,x2 ,···, xn} and{y1 ,y2 ,···, yn},aretheyequal?
3SUM:
Given a set {x1 , x2 ,··· , xn }, does it contain 3 elements xi, xj, xk, suchthat xi +xj +xk =0?
Note that the decision tree model cannot give such results, since each of these problems has only two possible outcomes: YES or NO.
78
SPECIAL PURPOSE
SORTING
ALGORITHMS
79
General Purpose Sorting:
Comparisons, Decision Tree, Algebraic Decision or Computation Tree …
Suppose you want to sort n numbers
with the pre-condition that each number is 1, 2, or 3.
How would you sort them?
We already saw that 3-Partition can sort them in-place in O(n) time.
Pre-cond: … Given universe of item values is finite (preferably “small”).
E.g., integers in [1 .. K] or [1 .. nd ] or [D digit integers in base B] (where K, d, D, B are given constants).
We can use special purpose sorting algorithms.
They break the W(n log n) lower bound barrier.
They are outside the algebraic computation/comparison model.
E.g., they use floor/ceiling integer rounding, use value as array index, …
Examples of Special Purpose Sorting Algorithms: Bucket Sort, Distribution Counting Sort,
Radix Sort, Radix Exchange Sort, …
80
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K)
Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n Post-Cond: A is rearranged into sorted order
1. for v 0 .. K-1 do Count[v] 0
2. for t 1 .. n do Count[A[t]] Count[A[t]] + 1
§ initialize § increment
§ Count[v] = # input items A[t] = v . . . More steps to come
end
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
n = 10, K = 4
Count = 2 | 3 | 2 | 3
0123 81
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2
3. for v 1 .. K-1 do Count[v] Count[v] + Count[v –1]
§ aggregate
§ Now Count[v] = # input items A[t] v
§ Count[v] = Last output index for item with value v . ..
end
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 Temp= |||||||||
n = 10, K = 4
2 | 5 | 7 | 10
2|3|2|3
Count =
0123 82
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
9 = Temp array position for next 3
Count= 2|5|7|10 0123
83
|||||||||
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
Count= 2|5|7|9 0123
||||
1
|||||
3
4
84
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
Count= 2|4|7|9 0123
|||
1
|
1
|||||
3
3
85
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
6
Count= 2|3|7|9 0123
86
|||
1
|
1
||
2
|||
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
1
Count= 2|3|6|9 0123
87
|
0||
1
|
1
||
2
|||
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
5
Count= 1|3|6|9 0123
88
|
0||
1
|
1
|
2|
2
|||
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
8
Count= 1|3|5|9 0123
89
|
0||
1
|
1
|
2|
2
||
3
|
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
Count= 1|3|5|8 0123
|
0|
1|
1
|
1
|
2|
2
||
3
|
3
2
90
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 3
Temp =
7
Count= 1|2|5|8 0123
91
|
0|
1|
1
|
1
|
2|
2
|
3
|
3
|
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
0
Count= 1|2|5|7 0123
92
0
|
0|
1|
1
|
1
|
2|
2
|
3
|
3
|
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3
4. for tndownto1do
Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
. ..
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3 n = 10, K = 4
Temp =
Count= 0|2|5|7 0123
93
0
|
0|
1|
1
|
1
|
2|
2
|
3
|
3
|
3
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K) § O(n + K) Time & Space Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n
Post-Cond: A is rearranged into sorted order
Steps 1, 2, 3, 4
5. for t 1 .. n do A[t] Temp[t]] § copy items back into A
. ..
end
1 2 3 4 5 6 7 8 9 10
Example: A = 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3 Temp =
Count= 0|2|5|7 0123
n = 10, K = 4
0
|
0|
1|
1
|
1
|
2|
2
|
3
|
3
|
3
94
Distribution Counting Sort
Algorithm CountingSort(A[1..n], K)
Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n Post-Cond: A is rearranged into sorted order
1. for v 0 .. K-1 do Count[v] 0
2. for t 1 .. n do Count[A[t]] Count[A[t]] + 1
§ Count[v] = # input items A[t] = v
3. for v 1 .. K-1 do Count[v] Count[v] + Count[v –1]
§ Now Count[v] = # input items A[t] v
§ Count[v] = Last output index for item with value v
§ initialize § increment
§ aggregate
4. for tndownto1do Temp[Count[A[t]] A[t]
Count[A[t]] Count[A[t]] –1 end-for
5. for t 1 .. n do A[t] Temp[t]]
end
§stablesort
§ place items in final position Temp array
§ decrement to preceding position
§ copy items back into A
O(n + K) Time & Space
95
end
Bucket Sort: Deterministic Version
Algorithm BucketSort(A[1..n], K)
Pre-Cond: input is array A[1..n], each A[t] [0 .. K-1], t = 1..n Post-Cond: A is rearranged into sorted order
for v 0 .. K-1 do Empty(B[v])
for t 1 .. n do Enqueue(A[t], B[A[t]]) t1
for v 0 .. K-1 do
§ initialize § fill buckets
while B[v] not empty do A[t] Dequeue(B[v])
t t +1 end-while
§ O(n + K) Time & Space
§ empty buckets back into array in order
0 v
Use K buckets B[0..K-1]. Each bucket B[v] is a queue
for stable sorting.
B[0..K-1]
K-1
96
Radix Sort
Sorting on digits from least significant to most significant digit position.
Algorithm RadixSort(A[1..n], D, B) § O(D(n + B)) Time Pre-Cond: input is array A[1..n], A[t] is a D digit integer in base B, t = 1..n Post-Cond: A is rearranged into sorted order
for d 0 .. D-1 do stable sort A[1..n] on digit d (e.g., Bucket or Counting Sort)
LI: A[1..n] is sorted on the d least significant digits
end
45 4 56 8 19 3 86 5 30 1
5 6 0 6 9
3 4 5 8 8
3 4 8 5 1
05 53 64 68 98
3 8 8 4 5
19 8 30 5 45 3 56 8 86 4
97
Radix Sort: Proof of Loop Invariant
:
: …… :
: …… :
:
Xd Yd
Xd-1 … X0 Yd-1 … Y0
:
: X[d..0] :
Y[d..0] :
:
Proof: X appears before Y X[d] Y[d] (by sorting in iteration d)
Loop Invariant by Induction on d:
Induction Hypothesis:
at the end of iteration d:
X appears before Y X[d..0] Y[d..0] :
Case 1: X[d] < Y[d] Case 2: X[d] = Y[d]
X[d..0] < Y[d..0]
X[d-1..0] appeared before Y[d-1..0] in previous iteration (by stable sorting)
X[d-1..0] Y[d-1..0] (by Induction Hypothesis) (null for the basis)
X[d..0] Y[d..0].
98
Radix Sort: the wrong way
1 3 4 5 8
9 0 5 6 6
30 45 56 86 19
5 3 8 4 8
4 5 1 8 3
538 685 983 648 054
4 53 8 64 3 05 5 68 1 98
Explain why it’s NOT working correctly.
99
Radix Exchange Sort
Sorting on most significant digit first á la QuickSort Partitioning. First call: RadixExchangeSort( A[1..n], D-1, B).
Algorithm RadixExchangeSort(A[s..t], d, B) § O(D(n + B)) Time Pre-Cond: array A[s..t] is sorted on digits d+1 .. D-1.
Post-Cond: A[s..t] is sorted order on all digits 0 .. d, d+1 .. D-1
if d < 0 or s ≥ t then return
Partition A[s..t] into B contiguous (possibly empty) subarrays A[s(v) .. t(v)],
v =0..B-1, where digit d of every item in A[s(v) .. t(v)] is v. for v 0 .. B-1 do RadixExchangeSort(A[s(v)..t(v)], d-1, B)
end
d d-1 ..... 0
0 0 0
1 1 1
2 2 2
First partition
on digit d position.
Then separately sort each of these sub-arrays on lower order digits recursively.
100
1 0 1 0 0 1 1 0 1
0 01 10 0 11 1 0 01 10 1 11 0 01 1 11 1 01 0
Radix Exchange Sort: Binary Example
0 0 0 0
00 01
0 10 0
0 10 1
01 11
1 00 1
1 01 0
1 01 1
1 11 0
1 11 1
1 1 1 1 1
1 0 1 1
0 1 1 0 0
00 01 01 11
01 11 10 11 10
00
01 01 01
10 10 10
11 11
0
0 0 1
0 1 1
1 1
1
1 0
00 0
0 10 0 10
01 1
1 00
1 01 1 01
1 11 1 11
1
0 1 1
1 1 0
0 1
1
1
1 0
1 0
101
Quiz Question
INPUT: array A[1..n], each element is a positive integer at most n2. OUTPUT: array A in sorted order.
QUESTION: How fast can this be done?
ANSWER:
CountingSort or BucketSort will take Q(n2) TIME and SPACE. That’s bad.
Use Radix Sort. Choose parameters D & B to minimize:
Time = O(D(n + B)).
X [1 .. n2] can be thought of as 2 digits in base n: X –1 = (X1 X0)n = n X1 + X0
X1 = (X –1) div n
X0 = (X –1) mod n
Choose D = 2, B = n. Time = O(D(n+B)) = O(n).
102
SELECTION
Find me the median property value in Ontario and the top 10% student SAT scores in North America
103
INPUT: OUTPUT:
The Selection Problem
A sequence A= a1 , a2 ,··· , an of n arbitrary numbers, and an integer K, 1 K n.
The Kth smallest element in A. That is, an element xA such that there are at most K-1 elements yA that satisfy y < x, but there are at least K elements yA that satisfy y x.
Example: A = 12, 15, 43, 15, 62, 88, 76 .
K: 1 2 3 4 5 6 7
Kth smallest: 12 15 15 43 62 76 88
Applications:
1. Order Statistics, Partitioning, Clustering, ....
2. In divide-and-conquer: divide at the median value, i.e., with K = n/2.
Solution 1: Sort A, then return the element at position K in the sorted order. This takes W(n log n) time in the worst case.
O(n) time solution for some special values of K, e.g.,
K=1 minimum element. K=n maximum element.
WLOGA: K n/2 (the median value): Kth smallest = (n-1-K)th largest.
104
Solution 2
• How would you find the 2nd smallest element in A, i.e., with K = 2?
• Incrementally scan A and keep track of the K smallest items (1st & 2nd smallest). • Generalize this idea using a heap:
Incrementally scan A[1..n] and rearrange the items so that A[1..K] is a MAX HEAP
holding the K smallest items seen so far. 1Kt
A = K smallest in A[1..t] Not yet scanned Max Heap
n
If the next item A[t] is too large, discard it. If A[t] is less than A[1]
(the Kth smallest so far), remove A[1] from the heap and place A[t] in the heap:
Algorithm Select(A[1..n], K)
ConstructMaxHeap(A[1..K]) § O(K) time, heap size = K for t K+1 . . n do § O(n) iterations
if A[t] < A[1] then A[t] A[1]
DownHeap(A,1) § O(log K) time
return A[1] end
Time = O( n log K). This is O(n) if K = O(1). 105
Solution 3
• Turn A[1..n] into a MIN HEAP of size n, then do K successive DeleteMins. The K smallest items will come out in sorted order.
Algorithm Select(A[1..n], K)
ConstructMinHeap(A[1..n]) for t 1 .. K do
x DeleteMin(A) return x
end
Time = O( n + K log n).
This is O(n) if K = O(n/log n).
Getting closer to covering up to the median range K = n/2
§ O(n) time, heap size = n § K iterations
§ O(log n) time
Another reason why we want Construct Heap in linear time
106
Solution 4: Randomized QuickSelect
• Hoare: Adapt the QuickSort strategy. Luckily we need to do only one of the two
possible recursive calls! That saves time on average.
Algorithm QuickSelect(S, K)
§ Assume 1 K |S|. Returns the Kth smallest element of S.
if |S| =1 then return the unique element of S p a random element in S
Partition S: S< { x S : x < p } S> { x S : x > p }
Assume adversary picks the larger recursive call
if | S< | K then return QuickSelect(S< , K) elseif |S| – |S> |Kthenreturn p
else return QuickSelect(S> , K – | S| + | S> | )
end
T(|S|) = max{ T(| S< |) , T(| S> |) } + Q( |S| ), T(n) = Q(1), for n=0,1.
S< : x < p S= : x = p S> : x > p
107
QuickSelect Running Time
n
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = max{T(i) , T(n-i-1)} + Q(n), T(n) = Q(1), for n=0,1.
Worst-Case:
T(n) = maxi { max{T(i) , T(n-i-1)} + Q(n) : i = 0 .. n –1 } = maxi { T(i) + Q(n) : i = n/2 .. n –1 }
= T(n – 1) + Q(n)
= Q(n2)
108
QuickSelect Running Time
n
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = max{T(i) , T(n-i-1)} + Q(n), T(n) = Q(1), for n=0,1.
Best-Case:
T(n) = mini { max{T(i) , T(n-i-1)} + Q(n) : i = 0 .. n –1 }
= mini { T(i) + Q(n) : i = n/2 .. n –1 } =T(n/2)+ Q(n)
= Q(n)
109
QuickSelect Running Time
n
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = max{T(i) , T(n-i-1)} + Q(n), T(n) = Q(1), for n=0,1.
Expected-Case:
T(n) = avei { max{T(i) , T(n-i-1)} + Q(n) : i = 0 .. n –1 } n / 2 n 1
i0 i1 n/2
differs from 2 QuickSort n
= Q(n)
1 T(ni1) T(i)Q(n) n
n 1 i n / 2
T(i) Q(n)
(use guess-&-verify method)
110
QuickSelect Running Time
S< : x < p
i
Worst-Case: Expected-Case: Best-Case:
n
p S> : x > p
n – i –1
T(n) = Q(n2) T(n) = Q(n) T(n) = Q(n)
The following question persisted for a while:
Is Selection as hard as Sorting in the worst case?
Does finding the median require W(n log n) time in the worst case?
But then came along the next development …………….. P.T.O.
111
Solution 5: Improved QuickSelect S< : x < p S= : x = p S> : x > p
T(|S|) = max{ T(| S< |) , T(| S> |) } + Q( |S| ), T(n) = Q(1), for n=0,1.
Ensure that neither of the two potential recursive calls is too large. How?
Pick the pivot more carefully rather than completely at random. How?
If the pivot is the median element, then the recursive call has size at most n/2.
But that’s like hitting the jackpot every time!
Make sure pivot is no more than a certain percentage away from median. How?
Use a deterministic sampling technique:
Can we somehow make a + b < 1? Let’s say, a 20% sample (i.e., one out of every 5 elements).
That’s n/5 element sample set.
That would give us T(n) = Q(n) ! P.T.O.
Let the pivot be median of this sample set, found recursively in T(n/5) time.
How close is this pivot to the true median of all the n elements?
Its ranking can vary from 10% to 90% (depending on the chosen sample). Why?
So, the larger recursive call can be as bad as T(9n/10).
T(n) = T(9n/10) + T(n/5) + Q(n) gives T(n) = Q(n1e) = w(n log n).
Any hope with this strategy?
112
T(n) = T(an) + T(bn) + Q(n)
with a + b > 1.
Solution 5: Improved QuickSelect
Pick the 20% sample itself more carefully. How?
Scan through the n elements and pick one out of each 5 elements.
Consider one of these 5 element groups.
If you were to pick one out of this 5, which one would you pick?
Pick median of this 5 element group in O(1) time.
So, in O(n) time we can pick our sample set M of n/5 group medians.
Now recursively Select pivot p to be the median of the sample set M.
S<: x
: x>p
we have max { | S< | , | S> | } < 3n/4.
M
shown in sorted order
Elements known to be p
p
113
Solution 5: Improved QuickSelect
Pick the 20% sample itself more carefully. How?
Scan through the n elements and pick one out of each 5 elements.
Consider one of these 5 element groups.
If you were to pick one out of this 5, which one would you pick?
Pick median of this 5 element group in O(1) time.
So, in O(n) time we can pick our sample set M of n/5 group medians.
Now recursively Select pivot p to be the median of the sample set M.
S<: x
: x>p
CLAIM: With this pivot p, we have max { | S< | , | S> | } < 3n/4. We have improved 90% to 75%, that is, 9n/10 to 3n/4.
The new recurrence is:
T(n) = T(3n/4) + T(n/5) + Q(n)
75% + 20% = 95% < 100%
Why 5
is chosen as group size?
114
Which gives the solution T(n) = Q(n).
The complete algorithm is shown on the next slide.
Q(1)
Q(n) T(n/5)
Q(n) T(3n/4)
Solution 5: Improved QuickSelect [Blum, Floyd, Pratt, Rivest, Tarjan, 1972]
Algorithm Select(S , K) § O(n) worst-case time § Assume 1 K |S|. Returns the Kth smallest element of S.
if |S| < 100 then sort S; return Kth element in sorted sequence S
g |S|/5 § -------------- sample size
divide S into g groups M1, M2, ..., Mg of 5 elements each (some leftover) for t 1 .. g do mt median of Mt
M {m1, m2, ... , mg } § -------------- the sample set of size g
p Select( M , g/2 ) §-------------- pivot = median of sample set M Partition S: S< { x S : x < p }
S> { x S : x > p }
end
115
if | S< | K then return Select (S< , K) elseif |S| – |S>|K thenreturn p
else return Select(S> , K – | S| + | S> | )
Upper Bound
&
Lower Bound
Techniques
116
Upper Bound & Lower Bound Techniques Upper Bound Methods: Algorithm Design Methods (so far):
Iteration
Recursion
Incremental
Iterative or Recursive Doubling Divide-&-Conquer Prune-&-Search
Lower Bound Methods:
Information Theory Decision Tree
Algebraic Computation Tree Problem Reduction Adversary Argument
117
• Examples:
• Search:
• Prune:
• Recur:
• Time:
• When:
Binary Search
Linear Time Selection algorithm.
More appear in Exercises at the end of this slide & later in the course….
Perform just enough computation to detect at least a certain fraction of the input data as irrelevant whose removal will not affect the outcome.
remove these irrelevant items from further consideration. repeat the process on the remaining data items.
With each iteration, # of remaining data items is shrinking geometrically. So, the time for the first iteration dominates the entire process.
This method can be applied to problems with small output, e.g., a single data item like the Kth smallest, rather than an elaborate output structure.
Prune-&-Search Method
118
Reduction Lower Bound Technique Algorithmfor “old”problemA
In
A
input transform
Any InB Algorithm for “new”
problem B
OutB
output transform
Out A
If the input & output transforms can be done “fast enough” that they are not the bottleneck, then
a lower-bound on time complexity of the “old” problem A implies
a lower-bound on time complexity of the “new” problem B.
so
119
Example Reduction
A) Element Uniqueness: Are any two elements of input sequence x1 , x2 ,··· , xn equal?
We already know this has W(n log n) lower bound in the Algebraic Computation Tree Model. B) Minimum Gap: Are there any two elements of the input sequence x1 , x2 , ···, xn
whose absolute value difference is a given number D? We can “reduce” problem A to B to get a lower bound on B.
The argument for this reduction is quite simple:
if we could solve B in less than W(n log n) time in the worst-case,
then we could also solve A in less than W(n log n) time in the worst-case by simply calling the “fastest” algorithm for B with input parameter D = 0.
Therefore, The Minimum Gap Problem also has the worst case time lower bound W(n log n).
120
Reduction Lower Bound Technique Algorithmfor “old”problemA
In
A
input transform
InB
Any Algorithm for “new” problem B
OutB
Out output A
transform
Example: Problem A: Problem B: Lower Bound:
Element Uniqueness.
Closest Pair of points in the plane. W(n log n)
121
Selection Lower Bound by Adversary Argument FACT: Selection always needs n-1 comparisons in the decision tree model.
Proof: we want to find the Kth smallest item in sequence S = a1, a2,···, an .
1. Let T be a correct decision tree for that task.
Assume elements of S are all distinct. T must work correctly on such S.
2. CLAIM: every leaf in T must have depth at least n-1.
3. Let X be a leaf in T that declares item am is the Kth smallest element of S.
4. Let P be the ancestral path of X in T.
5. We have to show that at least n-1 comparisons must have been made along P.
6. We will show this by constructing a directed graph G with vertex set S,
where comparisons along P appear as edges in G. Then argue that G must have at least n-1 edges.
T
P
G
am
x
122
Selection Lower Bound
7. Construct the directed graph G = (S, E) as follows:
E = { (ai , aj ) | comparison on path P that declares aj < ai, or aj ai }.
8. Clearly G is acyclic (contains no directed cycles) since S has distinct elements.
9. Remove from E every edge that is implied by transitivity.
10. Define:
S< = { ai | there is a directed path of length at least one in G from am to ai }. S> = { ai | there is a directed path of length at least one in G from ai to am }. S? = S – {am} – S< – S> .
11. These 3 subsets are disjoint and am belongs to none of them.
S<
S?
am
S>
123
Selection Lower Bound
S?
S< S>
am
12. CLAIM: S? = . Hence, |S<| + |S>| = n-1.
Suppose S? . Consider an element ai S? that minimizes D = | ai – am |. The adversary can shift the value of ai towards am by D + e ( for a very small positive real e). The relative ordering of every element in S has remained the same, except that now ai has moved to the opposite side of am.
All comparisons in T would still yield the same result, decisions would follow path P, and we would end up at leaf X, declaring that am is Kth smallest in S. This can’t be correct both times. Why?
124
T
P
x
Selection Lower Bound
G
S<
am S>
13. Since S< = { ai | there is a path of length at least 1 in G from am to ai }, every vertex in S< must have in-degree at least 1.
14. Since S> = { ai | there is a path of length at least 1 in G from ai to am }, every vertex in S> must have out-degree at least 1.
15. These imply that there must be at least |S<| + |S>| = n-1 edges in G.
16. Therefore, depth of X in T is at least n-1.
This completes the proof.
125
Median finding: improved lower bound
The best algorithm uses slightly less than 2.95n comparisons in the worst case.
The best lower bound is slightly more than 2n comparisons. (See Bibliography.)
Here we prove a weaker lower bound: 1.5(n – 1).
Call a comparison between x and y crucial
if either (x < y and y median) or (x > y and y median).
We showed that any selection algorithm makes at least n –1 crucial comparisons.
We now give an adversary argument to show that any median finding algorithm
must also make at least (n –1)/2 non-crucial comparisons. The idea is:
first, the adversary chooses some value (NOT some item) to be the median.
Then it assigns a label {N, L, S} to each item, and also values, as appropriate.
N = never participated in any comparison L = larger than the chosen median value S = smaller than the chosen median value
Initially each item is assigned an “N” label.
126
The Adversary’s Strategy
Algorithm compares
Adversary responds
(N,N)
assign one item to be larger than the median, one smaller; result is (L,S)
(S,N) or (N,S)
assign the N-item to be larger than the median; result is (S,L) or (L,S)
(L,N) or (N,L)
assign the N-item to be smaller than the median; result is (L,S) or (S,L)
(S,L) or (L,S) or (S,S) or (L,L)
consistent with previously assigned values
127
Count Comparisons
This strategy continues until (n-1)/2 S’s (or (n-1)/2 L’s) have been assigned.
If at some point (n-1)/2 S’s are assigned, then the adversary assigns the remaining
items to be greater than the median, except for one, which IS the median.
A similar thing is done if (n-1)/2 L’s have been assigned.
In any case, the last item assigned is always the median.
CLAIM: This strategy always forces the algorithm to perform
at least (n-1)/2 non-crucial comparisons.
Proof: Any time an N-item is compared, a non-crucial comparison is done (except at the very end, when a crucial comparison may be done with the median itself). The least number of comparisons with N-items that can be done is (n-1)/2.
The total number of comparisons is therefore at least n–1 +(n–1)/2 =1.5(n–1).
128
Bibliography
• C.A.R. Hoare, “Quicksort,” Computer Journal, 5(1):10-15, 1962.
• J. W. J. Williams, “Algorithm 232 (HEAPSORT),” Communications of the ACM, 7:347-348,
1964.
• Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, Robert E. Tarjan,
“Time Bounds for Selection,” Journal of Computer and System Sciences, 7(4):448-461, 1973.
• Dorit Dor, Uri Zwick, “Median Selection Requires (2+e)n Comparisons,” SIAM Journal on Discrete Mathematics, 14(3):312-325, 2001.
129
Exercises
130
1. The SkyLine Problem:
Given the exact locations and shapes of n rectangular buildings, in arbitrary order in a city, compute the skyline (in two dimensions) of these buildings, eliminating hidden lines.
An example of a building is shown in Fig (a) below; an input is shown in Fig (b); and its corresponding output is shown in Fig (c). We assume the bottoms of all the buildings lie on a horizontal line (the horizon).
Building B(k) is represented by a triple of real numbers (Lk , Hk, Rk). See Fig (a).
Lk and Rk denote the left and right x coordinates of the building, respectively, and Hk denotes the height of the building.
A skyline is a list of (alternating) x coordinates and heights connecting them arranged in order from left to right. For instance, the buildings in Fig (b) correspond to the following input:
(1, 6, 5), (2, 3, 7), (3, 9, 9), (11, 13, 13), (12, 5, 20), (16, 7, 22).
The skyline in Fig (c) is represented by the sequence: (1, 6, 3, 9, 9, 0, 11, 13, 13, 5, 16, 7, 22, 0 ). [Note: all bold red numbers above indicate height.]
a) Design and analyze an O(n log n) time divide-and-conquer algorithm to solve the Skyline Problem.
b) Now suppose the input list of buildings is given in the sorted order of their left x coordinate, i.e., L1 L2 L3 … Ln. Can the skyline problem be solved faster in this case? Explain.
Hk
Lk (a) Rk
(b) (c)
131
2. k-wayMerge:GiveanO(nlogk)timealgorithmtomergeksortedlistsoftotalsizenintoone sorted list of size n. [Hint: use a min heap for k-way merging.]
3. Iterative MergeSort: We described an implementation of MergeSort by recursive divide-&- conquer. MeregeSort can also be implemented iteratively. The idea is to initially consider each of the n input elements as sorted lists of size 1. Then in a round-robin fashion merge these sorted lists in pairs into larger size but fewer lists until there is only one sorted list remaining. That is the output sorted list. Give an iterative implementation of this version of MergeSort by keeping the sorted lists in a queue. Analyze the worst-case time complexity of your implementation.
4. Median of 2 sorted arrays: Let X[1..n] & Y[1..n] be two n-element sorted arrays. Give an O(log n) worst-case time algorithm to find the median of the 2n elements that appear in X and Y.
[Hint: use divide-&-conquer or prune-&-search.]
5. Stack depth for QuickSort: The QuickSort algorithm we described contains two recursive calls. Compilers usually execute recursive procedures by using a stack that contains pertinent information (that includes the parameter values) called stack frame, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its stack frame is pushed onto the stack; when it terminates, its stack frame is popped. Let’s assume we want to sort array A[1..n]. The stack frame corresponding to a subarray to be sorted is the pair of extreme indices of that subarray, and takes O(1) memory cell space. The stack depth is the maximum number of stack frames on the stack at any time during the computation.
a) Describe a scenario in which the stack depth for QuickSort, as described in the course, is Q(n). b) Modify the code for QuickSort so that the worst-case stack depth is Q(log n).
You must maintain the O(n log n) expected running time of the algorithm.
[Hint: decide which of the 2 recursive calls to invoke first.] 132
6. Searching and Selection in a partially sorted matrix:
We are given a matrix A[1..n, 1..n] of nn real numbers such that elements in each row of A appear in non-decreasing sorted order, and elements in each column of A also appear in non- decreasing sorted order. (This is a specific partial ordering of the n2 matrix elements.) Design and analyze efficient algorithms for the following:
a) Find the number of negative entries in matrix A. [O(n) time is possible.]
b) Search in A for a given real number x: Find the maximum matrix entry A[i,j] that is less
than or equal to x, or report that all elements of A are larger than x. [O(n) time is possible.]
c) Select the Kth smallest element of A, where K is a given positive integer n2.
[We know O(n2) time is achievable even without the partial ordering. Any faster here?]
7. Weighted Median:
For n distinct elements x1 , x2 , …, xn with positive weights w1 , w2 , …, wn such that w1 + w2 + … + wn = 1, the weighted (lower) median is the element xk satisfying
xxwi1 and xxwi1. ik2ik2
a) Argue that the median of x1 , x2 , …, xn is their weighted median with wi = 1/n for i = 1..n.
b) Show how to compute the weighted median of n elements in O(n log n) worst-case time
using sorting.
c) Show how to compute the weighted median of n elements in O(n) expected time similar to
QuickSelect.
d) Show how to compute the weighted median in O(n) worst-case time using a linear time (un-
weighted) median finding algorithm such as the one we discussed in the course.
[Hint: use prune-&-search.] 133
8. Heap Delete: The heap operation Delete(A,t) deletes the item in node t from heap A.
Give an implementation of this operation that runs in O(log n) time on a max heap of size n.
9. d-ary Heap: A d-ary heap is like a binary heap, but non-leaf nodes have d children instead of 2.
a) How would you represent a d-ary heap in an array?
b) What is the height of a d-ary heap with n elements in terms of n and d?
c) Give an efficient implementation of DeleteMax in a d-ary max-heap.
Analyze its worst-case running time in terms of d and n.
d) Give an efficient implementation of Insert in a d-ary max-heap. Analyze its worst-case running time in terms of d and n.
e) Give an efficient implementation of IncreaseKey(A, t, K), which first sets
A[t] max{A[t], K} and then updates the d-ary max-heap structure appropriately. Analyze its worst-case running time in terms of d and n.
10. Sorting grid points:
Given n points on the n-by-n integer grid in the plane, efficiently sort these points by their distance from the origin. What is the worst-case time complexity of your algorithm? [Hint: use RadixSort.]
11. Small decision tree:
a) Show that every comparison based (i.e., decision tree) algorithm that sorts 5 elements, makes at least 7 comparisons in the worst-case.
b) Give a comparison based (i.e., decision tree) algorithm that sorts 5 elements using at most 7 comparisons in the worst case.
134
12. Average Gap:
We are given an arbitrary (unsorted) array A[1..n] of n >1 distinct real numbers. The kth gap of A, denoted Gk(A), is the difference between the (k+1)st smallest
and kth smallest elements of A, for k =1..n-1.
The minimum gap of A, denoted Gmin(A), is the minimum Gk(A) over all k=1..n-1. The average gap of A, denoted Gave(A), is the average of Gk(A) over all k=1..n-1. That is, Gave(A) = (G1(A) + G2(A) + … + Gn-1(A)) / (n-1).
We clearly see that Gmin(A) Gave(A).
a) Describe an efficient algorithm to compute Gmin(A). What is the running time?
b) Show that Gave(A) = ( max(A) – min(A)) /(n-1).
c) Use part (b) to show that Gave(A) can be computed in O(n) time.
d) Design and analyze an O(n) time algorithm that finds a pair of elements
(A[i],A[j]), i j, of array A such that Gmin(A) | A[i] – A[j] | Gave(A). (The answer may not be unique. Just return one valid pair.)
[Hint: use median selection and prune-&-search.]
13. MergingLowerBound:
We discussed the information theory lower bound on merging two sorted lists, each containing n elements, and showed the lower bound of 2n – 1⁄2 log n.
a) A tighter decision tree lower bound can be achieved as follows:
Using an adversary argument, show that if two elements are consecutive in the output sorted order and are from opposite lists, then they must be compared.
b) Use your answer to part (a) to show a lower bound of 2n –1 comparisons.
135
14. The decision tree model for comparison-based sorting of a partially ordered set:
In this problem, we consider sorting n distinct keys which are already partially sorted as described below. The only way we are allowed to sort the keys is by performing a comparison between a pair of keys, where the only information obtained from a comparison is which of the two keys is larger. (Thus, we are not allowed to look at the values of the keys.)
Let the given keys be x1 , x2 , …, xn. Let A = {x1 , x2 , x3}, and B = {x4 , x5 , …, xn}. Suppose that A has been completely sorted (and without loss of generality assume x1 < x2 < x3), and that B has been completely sorted (and without loss of generality assume x4 < x5 < ...< xn), but there have not been any comparisons made between any key in A and any key in B.
a) Exactly how many possible orderings among all n keys are still possible given the information above, i.e. in how many possible ways can {x1 , x2 , x3} as a triple fit into the ordering among the n-3 other keys (not necessarily in adjacent positions)?
b) From part (a), derive a lower bound (exact, not just asymptotic) on the remaining number of comparisons necessary to completely sort all n keys. State the argument you use to derive your lower bound.
c) From part (b), what is the lower bound on the number of comparisons to complete the sorting when n is 6? Give your lower bound as a positive integer.
d) Give a decision tree for the case when n is 6 for which the worst case number of comparisons is exactly the lower bound on the number of comparisons given in part (c).
136
15. [CLRS Problem 8-4, pp. 206-207,] Red-Blue Water Jugs:
Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.
It is your task to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This will tell you whether the red or the blue jug holds more water, or if they are of the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.
a) Describe a deterministic algorithm that uses Q(n2) comparisons to group the jugs into pairs.
b) Prove a lower bound of W(n log n) for the number of comparisons an algorithm solving this
problem must take.
c) Give a randomized algorithm whose expected number of comparisons is O(n log n), and
prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?
137
16. Show that the 2nd smallest of n given elements can be found with n + log n –2 comparisons in the worst-case. [Hint: Also find the smallest element. Play elimination tournament among elements.]
17. Show that 3n/2 –2 comparisons are necessary and sufficient in the worst case to find both the maximum and the minimum of n elements. [Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts. Use labels similar to the ones we used for the median finding adversarial lower bound argument.]
18. Show how the worst-case running time of QuickSort can be improved to O(n log n) using selection.
19. In the comparison based model, show that any selection algorithm that finds the Kth smallest element, can also find the K-1 smaller elements and the n-K larger elements without any additional comparisons.
20. Suppose that you have a “black-box” worst-case linear-time median finding subroutine. Give a simple, linear-time algorithm that solves the selection problem for arbitrary order statistics K using the black-box as a subroutine.
21. The Kth quantiles of an n-element sequence are the K-1 order statistics that divide the sorted permutation of the sequence into K equal-sized (to within ±1) contiguous subsequences.
Give an O(n log K) time algorithm to list the Kth quantiles of a given unsorted sequence of n items.
22. Describe an O(n) time algorithm that, given a set S of n distinct numbers and a positive integer K n, determines the K numbers in S that are closest in value to the median of S.
Example:
Let S = { 9,2,7,3,8,1,12 }. Median(S) = 7, and the 3 items with closest values to 7 are {7,8,9}.
138
23. The facility Location Problem (FLP): We are given a set P = {p1 , p2 , ..., pn} of n points in the d dimensional space. Each point is given by its d coordinates as real numbers. We want to compute the location of the optimum facility point q whose sum of distances to the input points is minimized. That is, find a point q that minimizes
d(q, p1) + d(q, p2) + d(q, p3) + ... + d(q, pn), where d(q, pi) denotes the distance between q and pi .
Imagine we want to establish a communication center (the facility location q) and run lines from that center to each of the users (the given points). The objective is to minimize the total length of the communication lines between the center and the users.
a) Consider the one dimensional version of FLP ( d = 1). How do you characterize the solution point? Show one dimensional FLP can be solved in O(n) time.
b) How would you solve the problem for d = 2 (the planar case) assuming the communication lines are only allowed to go along horizontal and vertical line segments with bends in between. (Suppose the communication lines in the city of Manhattan should follow along the streets which are all North-South or East-West.) In the Manhattan metric, the distance
between points q = (x,y) and pi = (xi , yi ) is (See the illustrative figure below.)
y
yi
y
d(q, pi) = | x – xi | + | y – yi | . pi
q
x xi
139
x
24. The Majority Problem (MP): We are given a sequence S of n elements. A majority value, if it exists, is one that appears more than n/2 times in the input sequence. The problem is to determine if S has a majority element, and if so find it.
a) SupposeweareallowedtocomparepairsofelementsofSusingthecomparisonsfromthe set { = , , < , , > , }. Within this model we can solve MP in O(n log n) worst-case time by first sorting S. Describe the rest of the process.
b) Within the same comparison based model as in part (a), show the problem can be solved in O(n) worst-case time using Median Selection.
c) Now suppose the only comparisons we are allowed to make are from the set { = , }. So, we cannot sort. Show how to solve MP in worst-case O(n log n) time in this model using divide- &-conquer.
d) Within the same comparison based model as in part (c), show MP can be solved in O(n) worst-case time. [Hint: think about our solution to the VLSI chip testing problem in LS4.]
e) Here’sanotherdivide-and-conquerapproachtoanswerpart(d).
First assume n = 2k where k is a non-negative integer.
Pair up elements of A arbitrarily, to get n/2 pairs. Look at each pair: If the two elements are different, discard both of them; if they are the same, keep just one of them.
Show that after this procedure there are at most n/2 elements left, and that they have a majority element if A does. Turn this idea into an O(n) time algorithm that finds the majority element of A if there is one.
If n is not an integer power of 2, then we have the following:
Counter-example: (1,1, 1,1, 2,2, 2) has majority (1,1,2,2) has no majority.
Revise your algorithm so that it works correctly for all n.
140
25. A Loading Problem: We are given a set S of n items with weights specified by positive real numbers wi , i=1..n, and a truck with load weight capacity specified by a positive real number L. We want to load the truck with as many items as possible without exceeding its load capacity. That is, we want to find a maximum cardinality subset C S such that the sum of the item weights in C does not exceed the truck load capacity L.
(a) Briefly describe an O(n) time algorithm to solve this problem if S is given in sorted order. (b) Describe an O(n) time algorithm to solve this problem if S is given in arbitrary unsorted
order. [Hint: use median selection and prune-&-search.]
26. Significant Inversions: We are given a sequence of n arbitrary but distinct real numbers
a1 , a2 , ··· , an . We define a significant inversion to be a pair i < j such that ai > 2 aj. Design and analyze an O(n log n) time algorithm to count the number of significant inversions in the given sequence.
27. Lower Bound on the Closest Pair Problem:
The Closest Pair Problem asks to find the closest pair of points among a given set of n points in the plane. In the previous slide we claimed that the worst-case time complexity of this problem is W(n log n). Prove this lower bound using the reduction technique.
28. Lower Bound on BST Construction:
(a) Given a Binary Search Tree (BST) holding n keys, give an efficient algorithm to print those keys in sorted order. What is the running time of the algorithm?
(b) Within the decision tree model derive a lower bound on the BST construction problem, i.e., given a set of n keys in no particular order, construct a BST that holds those n keys.
141
29. Lower Bound on Priority Queues:
Is there a priority queue that does both Insert and DeleteMin in at most O(log log n) time? Explain.
30. Lower Bound on Sorting Partially Sorted List:
Let A[1..n] be an array of n elements such that we already know A[1 .. n-100] is sorted and A[n-99 .. n] is also sorted. Establish a worst-case decision tree lower bound for sorting the entire array A[1..n].
31. Time Bound on A Special Sorting Problem:
You are given a sequence of n integers that contains only log n distinct integer values (but we don’t know which integer values).
a) Design an algorithm to sort this sequence in O (n log log n) time.
[Hint: use a balanced Binary Search Tree where each node holds a distinct key and a pointer to the list of items with value equal to that key.]
b) Why does this run-time not violate the comparison based sorting lower bound of W(n log n) comparisons?
142
END
143