程序代写代做代考 compiler algorithm scheme decision tree discrete mathematics data structure information theory AI Sorting & Selection

Sorting & Selection

EECS 3101
Prof. Andy Mirzaian
Sorting
&
Selection

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) .
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.
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 .
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.,
Pile 1: A – F
Pile 2: G – L
Pile 3: M – S
Pile 4: 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
S< : x : x > p
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 § pivot item, why random? 3-Partition S into: § we already discussed this S<  { x  S : x  { x  S : x > p }
S’<  QuickSort(S<) § Exercise Question: S’>  QuickSort(S>) § which recursive call first?!
return  S’< , S= , S’> 
end

T(|S|) = T(| S< |) + T(| S> |) + Q( |S| ), T(n) = Q(1), for n=0,1.
8

QuickSort Running Time
S< : x : x > p

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
S< : x : x > p

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
S< : x : x > p

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 }

= Q(n log n)
(full history recurrence already discussed)
11

Full History Recurrence: QuickSort

1. Multiply across by n (so that we can subsequently cancel out the summation):
2. Substitute n-1 for n:

3. Subtract (2) from (1):

4. Rearrange:

5. Divide by n(n+1) to make
LHS & RHS look alike:

6. Rename:

7. Simplified recurrence:

8. Iteration:

9. Finally:
nth Harmonic
number

Why Randomize?
S< : x : x > p

n – i –1
Worst-Case: T(n) = Q(n2)
Expected-Case: T(n) = Q(n log n)
Best-Case: 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!
(extremely low).
FACT: Randomized QuickSort will take O(n log n) time
with probability very close to 1
on every input.
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.
4
5
6
7
1

36
16
23
17
51
18
27
19
44
20
69
21
20
22
27
23
47
24
33
25
59
26
46
27
48
8
62
9
77
10
34
11
53
12
61
13
41
14
29
15
73
81
66
54
2
3
84
74
91
15

Array as Binary Heap

A =
1
size[A]
max size
currently unused

A[t]
A[2t]
A[2t+1]
A[ t/2 ]
parent
node
left child
right child

h log n
1
n = size[A]

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 }.

76
88
74
82
56

48
18
74
92
1
2
3
4
5
6
7
8
9
10
11
12

L
R

A[1]

x
y

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)
end

1
18

UpHeap Example

76
88
74
82
56

48
18
74
92
1
2
3
4
5
6
7
8
9
10
11
12
86

86
88
76
82
56

48
18
74
92
1
2
3
4
5
6
7
8
9
10
11
12

82
88
76
86
56

48
18
74
92
1
2
3
4
5
6
7
8
9
10
11
12

stop
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) end t 2t 2t+1 20 DownHeap Example 94 76 88 74 82 56 68 68 48 18 74 92 1 2 3 4 5 6 7 8 9 10 11 12 26 94 26 88 74 76 56 68 68 48 18 74 92 1 2 3 4 5 6 7 8 9 10 11 12 94 74 88 26 76 56 68 68 48 18 74 92 1 2 3 4 5 6 7 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 h = log n n i 2i 1 t Most nodes are concentrated near the bottom with larger depths but smaller heights. Idea: DownHeap is better! 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 L R A[1] T(n) = T(|L|) + T(|R|) + O(log n)  T(n) = O(n) n 2i 1 t h-i h = log n 23 Construct Heap Example 14 62 92 26 23 56 83 12 94 88 51 42 1 2 3 4 5 6 7 8 9 10 11 12 24 DownHeap(A,t) t=6 Construct Heap Example 14 62 92 26 23 56 83 12 94 88 51 42 1 2 3 4 5 6 7 8 9 10 11 12 25 DownHeap(A,t) t=5 Construct Heap Example 14 62 92 26 23 12 83 56 94 88 51 42 1 2 3 4 5 6 7 8 9 10 11 12 26 DownHeap(A,t) t=4 Construct Heap Example 14 88 92 26 23 12 83 56 94 62 51 42 1 2 3 4 5 6 7 8 9 10 11 12 27 DownHeap(A,t) t=3 Construct Heap Example 14 88 92 26 23 12 83 56 51 62 94 42 1 2 3 4 5 6 7 8 9 10 11 12 28 DownHeap(A,t) t=2 Construct Heap Example 14 88 42 26 23 12 83 56 51 62 94 92 1 2 3 4 5 6 7 8 9 10 11 12 29 DownHeap(A,t) t=1 Construct Heap Example 14 88 42 26 94 12 23 56 51 62 83 92 1 2 3 4 5 6 7 8 9 10 11 12 30 Construct Heap Example 94 62 42 26 88 12 23 56 51 14 83 92 1 2 3 4 5 6 7 8 9 10 11 12 MAX HEAP 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): Construct a priority queue containing the set S of items. Insert(x, S): Insert new item x into S (duplicate values allowed) DeleteMax(S): 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) MakeEmptyHeap(A) size[A]  0 O(n) ConstructHeap(A[1..n]) discussed already O(log n) Insert(x,A) and DeleteMax(A) see below 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] 1 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. HEAP priority d[v] v GRAPH v t node[v] = t v 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 t  n downto 2 do A[t]  DeleteMax(A) end 35 HeapSort Example 94 76 88 74 82 56 68 68 48 18 74 92 1 2 3 4 5 6 7 8 9 10 11 12 94 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 56 already constructed heap 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 12 Max Item swap 36 (pages 36 – 68) HeapSort Example 56 76 88 74 82 94 68 68 48 18 74 92 1 2 3 4 5 6 7 8 9 10 11 12 56 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 12 37 DownHeap(A,1) HeapSort Example 56 76 88 74 82 94 68 68 48 18 74 92 1 2 3 4 5 6 7 8 9 10 11 12 56 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 11 38 HeapSort Example 92 76 56 74 82 94 68 68 48 18 74 88 1 2 3 4 5 6 7 8 9 10 11 12 92 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 18 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 11 Max Item swap 39 HeapSort Example 18 76 56 74 82 94 68 68 48 92 74 88 1 2 3 4 5 6 7 8 9 10 11 12 18 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 11 40 DownHeap(A,1) HeapSort Example 18 76 56 74 82 94 68 68 48 92 74 88 1 2 3 4 5 6 7 8 9 10 11 12 18 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 10 41 HeapSort Example 88 76 56 74 82 94 68 18 48 92 74 68 1 2 3 4 5 6 7 8 9 10 11 12 88 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 74 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 10 Max Item swap 42 HeapSort Example 74 76 56 88 82 94 68 18 48 92 74 68 1 2 3 4 5 6 7 8 9 10 11 12 74 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 10 43 DownHeap(A,1) HeapSort Example 74 76 56 88 82 94 68 18 48 92 74 68 1 2 3 4 5 6 7 8 9 10 11 12 74 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 9 44 HeapSort Example 82 74 56 88 76 94 68 18 48 92 74 68 1 2 3 4 5 6 7 8 9 10 11 12 82 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 48 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 9 Max Item swap 45 HeapSort Example 48 74 56 88 76 94 68 18 82 92 74 68 1 2 3 4 5 6 7 8 9 10 11 12 48 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 9 46 DownHeap(A,1) HeapSort Example 48 74 56 88 76 94 68 18 82 92 74 68 1 2 3 4 5 6 7 8 9 10 11 12 48 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 8 47 HeapSort Example 76 74 56 88 74 94 48 18 82 92 68 68 1 2 3 4 5 6 7 8 9 10 11 12 76 | 74 | 68 | 68 | 74 | 18 | 56 | 48 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 8 Max Item swap 48 HeapSort Example 48 74 56 88 74 94 76 18 82 92 68 68 1 2 3 4 5 6 7 8 9 10 11 12 48 | 74 | 68 | 68 | 74 | 18 | 56 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 8 49 DownHeap(A,1) HeapSort Example 48 74 56 88 74 94 76 18 82 92 68 68 1 2 3 4 5 6 7 8 9 10 11 12 48 | 74 | 68 | 68 | 74 | 18 | 56 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 7 50 HeapSort Example 74 48 56 88 74 94 76 18 82 92 68 68 1 2 3 4 5 6 7 8 9 10 11 12 74 | 74 | 68 | 68 | 48 | 18 | 56 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 7 Max Item swap 51 HeapSort Example 56 48 74 88 74 94 76 18 82 92 68 68 1 2 3 4 5 6 7 8 9 10 11 12 56 | 74 | 68 | 68 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 7 52 DownHeap(A,1) HeapSort Example 56 48 74 88 74 94 76 18 82 92 68 68 1 2 3 4 5 6 7 8 9 10 11 12 56 | 74 | 68 | 68 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 6 53 HeapSort Example 74 48 74 88 68 94 76 18 82 92 56 68 1 2 3 4 5 6 7 8 9 10 11 12 74 | 68 | 68 | 56 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 6 Max Item swap 54 HeapSort Example 18 48 74 88 68 94 76 74 82 92 56 68 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 6 55 DownHeap(A,1) HeapSort Example 18 48 74 88 68 94 76 74 82 92 56 68 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 5 56 HeapSort Example 68 48 74 88 56 94 76 74 82 92 18 68 1 2 3 4 5 6 7 8 9 10 11 12 68 | 56 | 68 | 18 | 48 | 74 | 74 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 5 Max Item swap 57 HeapSort Example 48 68 74 88 56 94 76 74 82 92 18 68 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 5 58 DownHeap(A,1) HeapSort Example 48 68 74 88 56 94 76 74 82 92 18 68 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 4 59 HeapSort Example 68 68 74 88 56 94 76 74 82 92 18 48 1 2 3 4 5 6 7 8 9 10 11 12 68 | 56 | 48 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 4 Max Item swap 60 HeapSort Example 18 68 74 88 56 94 76 74 82 92 68 48 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 4 61 DownHeap(A,1) HeapSort Example 18 68 74 88 56 94 76 74 82 92 68 48 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 3 62 HeapSort Example 56 68 74 88 18 94 76 74 82 92 68 48 1 2 3 4 5 6 7 8 9 10 11 12 56 | 18 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94 1 2 3 4 5 6 7 8 9 10 11 12 size[A] = 3 Max Item swap 63 HeapSort Example 48 68 74 88 18 94 76 74 82 92 68 56 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 3 64 DownHeap(A,1) HeapSort Example 48 68 74 88 18 94 76 74 82 92 68 56 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 2 65 HeapSort Example 48 68 74 88 18 94 76 74 82 92 68 56 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 2 Max Item swap 66 HeapSort Example 18 68 74 88 48 94 76 74 82 92 68 56 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 2 67 HeapSort Example 18 68 74 88 48 94 76 74 82 92 68 56 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 2 3 4 5 6 7 8 9 10 11 12 size[A] = 1 SORTED ARRAY 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,3,2 3,1,2 2,1,3 2,3,1 1 : 3 1 : 3 1,2,3 3,2,1 2 : 3 2 : 3 1 : 2 < < < < < >
>
>
>
>
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.

< >

S
Sn

ai : aj
x
S’ =
subset of S
consistent with
ai < aj S” = subset of S consistent with ai > aj
max { |S’| , |S”| }  ½ |S|
71

Information Theory Lower Bound on Sorting

< >

S
Sn

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!

worst-path down
log 1 = 0

Sorting Lower Bound:
length of worst path
down the decision tree is
 log n!
 W(n log n)

Information Theory Lower Bound

height
H
L leaves
Worst- case # of comparisons  H  log (# possible outcomes).
# of possible outcomes  L  2H

In a 3-way decision tree, it’s log base 3.
73

More Decision Tree Lower Bounds
# Leaves in T = 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
= S{ depth(x, T) : x is a leaf in T}
= S{ depth(x, T) : x is a leaf in L}
+ S{ depth(x, T) : x is a leaf in R}
= S{ 1 + depth(x, L) : x is a leaf in L}
+ S{ 1 + depth(x, R) : x is a leaf in R}
= mT + S{ depth(x, L) : x is a leaf in L}
+ S{ depth(x, R) : x is a leaf in R}
 mT + mL log mL + mR log mR (by Induction Hypothesis)
 mT + (½ mT)log(½ mT) + (½ mT)log(½ mT) (m log m is convex:
= mT log mT min at mL= mR = ½ mT)

L
R

mL leaves

mR leaves

mT leaves

mT  n!
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:
74

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.
FACT 2: 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?
log (# outcomes) = log (2n)! – 2 log n!  2n – ½ log n  W(n).

Answer: # outcomes =
Use eq. (3.18): approximation formula for n!, on page 57 of [CLRS]
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:
Given two sets {x1 , x2 ,··· , xn } and {y1 , y2 ,··· , yn }, do they intersect?

Set Equality:
Given two sets {x1 , x2 ,··· , xn } and {y1 , y2 ,··· , yn }, are they equal?

3SUM:
Given a set {x1 , x2 ,··· , xn }, does it contain 3 elements xi, xj, xk,
such that 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

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, …
General Purpose Sorting:
Comparisons, Decision Tree, Algebraic Decision or Computation Tree …
80

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
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4
2 | 5 | 7 | 10

2 | 3 | 2 | 3
0 1 2 3
Count =
| | | | | | | | |
Temp =

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4
2 | 5 | 7 | 10
0 1 2 3
Count =
| | | | | | | | |
Temp =

9 = Temp array position for next 3

3
83

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4
2 | 5 | 7 | 9
0 1 2 3
Count =
| | | | | | | | |
Temp =

1
3
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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4
2 | 4 | 7 | 9
0 1 2 3
Count =

1
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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4
2 | 3 | 7 | 9
0 1 2 3
Count =

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4
2 | 3 | 6 | 9
0 1 2 3
Count =

0
87

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
1 | 3 | 6 | 9
0 1 2 3
Count =
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
1 | 3 | 5 | 9
0 1 2 3
Count =
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
1 | 3 | 5 | 8
0 1 2 3
Count =
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4

1
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 t  n downto 1 do § stable sort Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
1 | 2 | 5 | 8
0 1 2 3
Count =
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 3

3
91

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 t  n downto 1 do § stable sort Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4

3
1 | 2 | 5 | 7
0 1 2 3
Count =

0
92

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 t  n downto 1 do § stable sort
Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
. . .
end
Example:
0 | 3 | 1 | 3 | 2 | 0 | 2 | 1 | 1 | 3
1 2 3 4 5 6 7 8 9 10
A =
n = 10, K = 4

3
0 | 2 | 5 | 7
0 1 2 3
Count =

0
93

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
Example:
1 2 3 4 5 6 7 8 9 10
0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3
A =
n = 10, K = 4
| | | | | | | | |
Temp =
1
3
1
2
0
2
3
1
3
0 | 2 | 5 | 7
0 1 2 3
Count =
0
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 § initialize
2. for t  1 .. n do Count[A[t]]  Count[A[t]] + 1 § increment
§ Count[v] = # input items A[t] = v
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
4. for t  n downto 1 do § stable sort Temp[Count[A[t]]  A[t] § place items in final position Temp array Count[A[t]]  Count[A[t]] –1 § decrement to preceding position
end-for
5. for t  1 .. n do A[t]  Temp[t]] § copy items back into A
end
O(n + K) Time & Space
95

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]) § initialize
for t  1 .. n do Enqueue(A[t], B[A[t]]) § fill buckets
t  1
for v  0 .. K-1 do § empty buckets back into array in order
while B[v] not empty do
A[t]  Dequeue(B[v])
t  t +1
end-while
end
§ O(n + K) Time & Space

B[0..K-1]
0
v
K-1
Use K buckets B[0..K-1].
Each bucket B[v] is a queue
for stable sorting.
96

Radix Sort
Algorithm RadixSort(A[1..n], D, B)
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
§ O(D(n + B)) Time
4 5 3
5 6 8
1 9 8
8 6 4
3 0 5

4 5 3
8 6 4 3 0 5 5 6 8
1 9 8

3 0 5 4 5 3
8 6 4 5 6 8
1 9 8

1 9 8 3 0 5 4 5 3
5 6 8 8 6 4
Sorting on digits from least significant to most significant digit position.
97

Radix Sort: Proof of Loop Invariant

:
:
…… Xd Xd-1 … X0
:
:
…… Yd Yd-1 … Y0
:
:

:
:
X[d..0]
:
:
Y[d..0]
:
:
Proof: X appears before Y  X[d]  Y[d] (by sorting in iteration d)

Case 1: X[d] < Y[d]  X[d..0] < Y[d..0] Case 2: X[d] = Y[d]  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]. Loop Invariant by Induction on d: Induction Hypothesis: at the end of iteration d: X appears before Y  X[d..0] Y[d..0] 98 Radix Sort: the wrong way 4 5 3 5 6 8 1 9 8 8 6 4 3 0 5 1 9 8 3 0 5 4 5 3 5 6 8 8 6 4 3 0 5 4 5 3 5 6 8 8 6 4 1 9 8 4 5 3 8 6 4 3 0 5 5 6 8 1 9 8 Explain why it’s NOT working correctly. 99 Radix Exchange Sort Algorithm RadixExchangeSort(A[s..t], d, B) 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 § O(D(n + B)) Time Sorting on most significant digit first á la QuickSort Partitioning. First call: RadixExchangeSort( A[1..n], D-1, B). 000 d d-1 ….. 0 Then separately sort each of these sub-arrays on lower order digits recursively. First partition on digit d position. 111 222 100 Radix Exchange Sort: Binary Example 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 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? Use Radix Sort. Choose parameters D & B to minimize: Time = O(D(n + B)). ANSWER: CountingSort or BucketSort will take Q(n2) TIME and SPACE. That’s bad.  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 The Selection Problem INPUT: A sequence A=  a1 , a2 ,··· , an  of n arbitrary numbers, and an integer K, 1  K  n. OUTPUT: The Kth smallest element in A. That is, an element xA such that there are at most K-1 elements yA that satisfy y < x, but there are at least K elements yA that satisfy y  x. 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. 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 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. 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). 1 K t n Not yet scanned Max Heap K smallest in A[1..t] A = 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: 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]) § O(n) time, heap size = n for t  1 .. K do § K iterations x  DeleteMin(A) § O(log n) time 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  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  { x  S : x > p }

if | S< |  K then return QuickSelect(S< , K) else if |S| – | S> |  K then return p
else return QuickSelect(S> , K – | S| + | S> | )
end
S< : x : x > p
T(|S|) = max{ T(| S< |) , T(| S> |) } + Q( |S| ), T(n) = Q(1), for n=0,1.
Assume adversary picks the larger recursive call
107

QuickSelect Running Time
S< : x : x > p

n – i –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)
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.
108

QuickSelect Running Time
S< : x : x > p

n – i –1
= mini { T(i) + Q(n) : i = n/2 .. n –1 }
= T(n/2) + Q(n)
= Q(n)
Best-Case:
T(n) = mini { max{T(i) , T(n-i-1)} + Q(n) : i = 0 .. n –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.
109

QuickSelect Running Time
S< : x : x > p

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 }

= Q(n)
(use guess-&-verify method)
differs from QuickSort
110

QuickSelect Running Time
S< : x : x > p

n – i –1
Worst-Case: T(n) = Q(n2)
Expected-Case: T(n) = Q(n)
Best-Case: 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 : 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:
Let’s say, a 20% sample (i.e., one out of every 5 elements).
That’s n/5 element sample set.
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(n1+e) = w(n log n).
Any hope with this strategy?
T(n) = T(an) + T(bn) + Q(n)
with a + b > 1.
Can we somehow make a + b < 1? That would give us T(n) = Q(n) ! P.T.O.  112 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. CLAIM: With this pivot p, we have max { | S< | , | S> | } < 3n/4. S< : x : x > p
Proof:

M
shown in
sorted order

Elements known to be  p
Elements known to be  p

Each 5 item group shown as a column, sorted from top to bottom.
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.
CLAIM: With this pivot p, we have max { | S< | , | S> | } < 3n/4. S< : x : x > p
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)

Which gives the solution T(n) = Q(n).

The complete algorithm is shown on the next slide.
75% + 20% = 95% < 100% Why 5 is chosen as group size? 114 Solution 5: Improved QuickSelect 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  { x  S : x > p }

if | S< |  K then return Select (S< , K) else if |S| – | S> |  K then return p
else return Select(S> , K – | S| + | S> | )
end
[Blum, Floyd, Pratt, Rivest, Tarjan, 1972]

Q(n)
T(n/5)
T(3n/4)
Q(n)

Q(1)
115

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

Prune-&-Search Method
Examples:
Binary Search
Linear Time Selection algorithm.
More appear in Exercises at the end of this slide & later in the course….

Search: Perform just enough computation to detect at least a certain fraction of
the input data as irrelevant whose removal will not affect the outcome.

Prune: remove these irrelevant items from further consideration.

Recur: repeat the process on the remaining data items.

Time: With each iteration, # of remaining data items is shrinking geometrically.
So, the time for the first iteration dominates the entire process.

When: 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.
118

Reduction Lower Bound Technique

input
transform

InA
Algorithm for “old” problem A
Any
Algorithm for “new” problem B
output
transform
InB
OutB
OutA
If the input & output transforms can be done “fast enough” so 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.
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

input
transform

InA
Algorithm for “old” problem A
Any
Algorithm for “new” problem B
output
transform
InB
OutB
OutA
Example:
Problem A: Element Uniqueness.
Problem B: Closest Pair of points in the plane.
Lower Bound: 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 .
Let T be a correct decision tree for that task.
Assume elements of S are all distinct. T must work correctly on such S.
CLAIM: every leaf in T must have depth at least n-1.
Let X be a leaf in T that declares item am is the Kth smallest element of S.
Let P be the ancestral path of X in T.
We have to show that at least n-1 comparisons must have been made along P.
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
x
P

122

Selection Lower Bound
Construct the directed graph G = (S, E) as follows:
E = { (ai , aj ) |  comparison on path P that declares aj < ai, or aj  ai }. Clearly G is acyclic (contains no directed cycles) since S has distinct elements. Remove from E every edge that is implied by transitivity. 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> .
These 3 subsets are disjoint and am belongs to none of them.

S< S>
S?

am
123

Selection Lower Bound
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?

S< S>
S?

am
124

Selection Lower Bound
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. 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.
These imply that there must be at least |S<| + |S>| = n-1 edges in G.
Therefore, depth of X in T is at least n-1.
This completes the proof.

T
x
P

S< S>

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

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.]
Design and analyze an O(n log n) time divide-and-conquer algorithm to solve the Skyline Problem.
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.

Lk
Rk
Hk
(a)
(b)

(c)

131

k-way Merge: Give an O(n log k) time algorithm to merge k sorted lists of total size n into one sorted list of size n. [Hint: use a min heap for k-way merging.]

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.

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.]

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.
Describe a scenario in which the stack depth for QuickSort, as described in the course, is Q(n).
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

Searching and Selection in a partially sorted matrix:
We are given a matrix A[1..n, 1..n] of nn 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:
Find the number of negative entries in matrix A. [O(n) time is possible.]
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.]
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?]

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

Argue that the median of x1 , x2 , …, xn is their weighted median with wi = 1/n for i = 1..n.
Show how to compute the weighted median of n elements in O(n log n) worst-case time using sorting.
Show how to compute the weighted median of n elements in O(n) expected time similar to QuickSelect.
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

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.

d-ary Heap: A d-ary heap is like a binary heap, but non-leaf nodes have d children instead of 2.
How would you represent a d-ary heap in an array?
What is the height of a d-ary heap with n elements in terms of n and d?
Give an efficient implementation of DeleteMax in a d-ary max-heap.
Analyze its worst-case running time in terms of d and n.
Give an efficient implementation of Insert in a d-ary max-heap.
Analyze its worst-case running time in terms of d and n.
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.

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.]

Small decision tree:
Show that every comparison based (i.e., decision tree) algorithm that sorts 5 elements,
makes at least 7 comparisons in the worst-case.
Give a comparison based (i.e., decision tree) algorithm that sorts 5 elements using
at most 7 comparisons in the worst case.
134

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).
Describe an efficient algorithm to compute Gmin(A). What is the running time?
Show that Gave(A) = ( max(A) – min(A)) /(n-1).
Use part (b) to show that Gave(A) can be computed in O(n) time.
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.]
Merging Lower Bound:
We discussed the information theory lower bound on merging two sorted lists,
each containing n elements, and showed the lower bound of  2n – ½ log n.
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.
Use your answer to part (a) to show a lower bound of 2n –1 comparisons.
135

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. 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)? 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. 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. 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 [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. Describe a deterministic algorithm that uses Q(n2) comparisons to group the jugs into pairs. Prove a lower bound of W(n log n) for the number of comparisons an algorithm solving this problem must take. 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 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.] 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.] Show how the worst-case running time of QuickSort can be improved to O(n log n) using selection. 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. 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. 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. 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 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. 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. 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 d(q, pi) = | x – xi | + | y – yi | . (See the illustrative figure below.) pi xi yi x y x y q 139 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. Suppose we are allowed to compare pairs of elements of S using the comparisons from the 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.
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.
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.
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.]
Here’s another divide-and-conquer approach to answer part (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

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.]

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.

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.

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

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.

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].

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

[
]
å
–
=
Q
+
–
–
+
=
1
n
0
i
)
n
(
)
1
i
n
(
T
)
i
(
T
n
1

)
n
(
)
i
(
T
1
n
0
i
n
2
Q
+
=
å
–
=

0
n
,
n
)
i
(
T
2
)
n
(
T
n
2
1
n
0
i
³
”
+
=
å
–
=

).
n
log
n
(
n
3
)
n
(
H
)
1
n
(
2
)
n
(
Q
)
1
n
(
)
n
(
T
Q
=
–
+
=
+
=

1
n
,
)
1
n
(
)
i
(
T
2
)
1
n
(
T
)
1
n
(
2
2
n
0
i
³
”
–
+
=
–
–
å
–
=

1
n
,
1
n
2
)
1
n
(
T
2
)
1
n
(
T
)
1
n
(
)
n
(
nT
³
”
–
+
–
=
–
–
–

1
n
,
1
n
2
)
1
n
(
T
)
1
n
(
)
n
(
nT
³
”
–
+
–
+
=

1
n
,
)
1
n
(
n
1
n
2
n
)
1
n
(
T
1
n
)
n
(
T
³
”
+
–
+
–
=
+

n
1
1
n
3
1)
n(n
1
–
2n

,
n
)
1
n
(
T
)
1
n
(
Q

,
1
n
)
n
(
T
)
n
(
Q
–
+
=
+
–
=
–
+
=

[
]
î
í
ì
=
³
”
–
+
–
=
+
0
n
for
0
1
n
)
1
n
(
Q
)
n
(
Q
n
1
1
n
3

]
0
)
0
(
T

[

0
n
,
n
)
i
(
T
n
2
)
n
(
T

:
2

Example
1
n
0
i
=
Þ
³
”
+
=
å
–
=

(
)
(
)
(
)
(
)
1
3
1
1
2
3
2
1
1
3
1
1
3
1
1
3
)
(
2
)
0
(
)
(
+
–
–
–
+
–
=
+
–
+
×
×
×
+
–
+
–
+
–
=
n
n
n
n
n
n
n
n
n
H
Q
n
Q

)
n
log
n
(
)
2
h
(
2
i
Time
h
h
0
i
i
Q
=
Q
=
÷
ø
ö
ç
è
æ
Q
=
å
=

)
n
(
)
1
(
2
)
2
j
(
2
2
j
2
)
i
h
(
Time
h
h
0
j
j
h
h
0
j
j
h
h
0
i
i
Q
=
Q
=
Q
=
÷
÷
ø
ö
ç
ç
è
æ
Q
=
÷
ø
ö
ç
è
æ
–
Q
=
å
å
å
=
–
=
–
=

!
n
!
n
)!
n
2
(
n
n
2
=
÷
ø
ö
ç
è
æ

ë
û
ë
û
)
n
(
)
i
(
T
)
1
i
n
(
T
n
1
n
2
/
n
1
i
2
/
n
0
i
1
Q
+
÷
÷
ø
ö
ç
ç
è
æ
+
–
–
=
å
å
–
+
=
=

)
n
(
)
i
(
T
1
n
2
/
n
i
n
2
Q
+
=
å
–
=

and

w
2
1
2
1
k
i
k
i
x
x
i
x
x
i
£
< å å >
< /docProps/thumbnail.jpeg

Related Posts