EECS 477 - 1/19/07
Alice and Wonderland
single elimination tounament
selection
randomized selection algorithm
selection in optimal linear time
lower bounds on selection
problem
given n totally ordered elements and 1<=k<=n,
find smallest element
only allowed to compare two elements
k=1
n-1 comparisons necessary and sufficient
k=2
random selection
rank(e, S)
returns rank of e in set of elements S
takes n-1 comparisons
QuickSelect(k, S)
pick random element
find Rank
if r=k
return e
if k
return quickselect(k, S<)
otherwise
return quickselect(k-r,S>)
want to show that Q(n) is linear
can't use unknown constant
must use constant c
prove that O(n) <= cn
lower bounds
median of medians algorithm
5 guys algorithm
find e that splits set in half
recurse on each half
select(k, S)
divide S into |S|/5
|
| |