Transcript novax

Lazy Select Algorithm.
Input: A set S of n elements from a totally ordered universe,
k-integer in [1,n].
Output: The k th smallest element of S, S(k).
1. Pick
n 3 / 4 elements of S, chosen independently and uniformly
at
random , with replacement; call this multiset R.
2. Sort R in O ( n 3 / 4 * log n ) steps using any optimal sorting algorithm.
3. Let l  max{
 
k
1/ 4
n
n,1} and
Let a=R(l) and b=R(h) .
rs (b)
Determine rs (a) and
h  min{ n1k/ 4   n , n 3 / 4 }
4.
If k< n
1/ 4
then P={y
n  n1/ 4 , let P={y
else if k >
else if k
S|y
n
1/ 4
b};
S|y

, n  n1/ 4 , let P={y
Check whether S(k)
P and |P|
a};
S|a
y
4n 3 / 4  2
.
b};
If not, repeat Steps 1-3 until such a set P found.
5.
By sorting P in O(| P | log | P |) steps, identify
which is S(k).
P( k rs ( a )1)
to identify a an b in S such that:
1.The element S(k) , that we seek, is in P.
2.The set P of elements is not very large, so that we can sort
inexpensively In Step5.
Theorem :
With probability
1  O(n 1/ 4 )
, LazySelect finds S(k) on
the first pass through Steps 1-5 , and thus performs only
2n+o(n) comparisons.
The probability to fail:
We fail if
1. either element a>S(k) or b<S(k).( In such a situation P does not contain
S(k) ).
2.P is too big.
When a > S(k) ?
Let
Xi 
Thus Pr[ X i
Pr[

1,
0,
if the i th random sampleis at most S ( k )
otherwise
 1 ]=k/n
X i  0 ]=1-k/n

1 i n3/ 4
n3 / 4
Let
X   Xi
i 1
X indicates the number of samples in R that are at most S(k).
What is the expected number of such a samples in R?
n3 / 4
n3 / 4
k
k
  E[ X ]   E[ X i ]   (0 * Pr[ X i  0]  1* Pr[ X i  1] )  n *  1/ 4
n n
i 1
i 1
3/ 4
Recall that
l 
k

n1 / 4
n
If X has an expected value then a and b are chosen good!
So what is the probability to fail?
Chebyshev: Pr[|X- | t* ]
Pr[|X-
1
t2
|
n ].
Lemma:
 (X ) 
2
n3 / 4

i 1
Xi
2
(Xi)
is a Bernoulli variable, with probability k/n for successes
and (1-k/n) for fail.
k
k
 ( X i )  * (1  )
n
n
2
 (X )  n
2
3/ 4
k
k
* ( ) * (1  )  n 3 / 4
n
n
1 2
1
Pr[| X   | n ]  Pr[| X   | n * ( X )]  ( 1/ 8 )  1/ 4
n
n
1/ 8
So , the probability that the element S(k) ,that we seek ,is in P is
1  O(
1
)
1/ 4
n
Note : the analysis of the second mode of failure we leave to diligent student.
The Stable Marriage Problem.
A monogamous, heterosexual society:
A:
a,b,c,d
a: A,B,C,D
B:
b,a,c,d
b: D,C,B,A
C:
a,d,c,b
c:
A,B,C,D
D:
d,c,a,b
d:
C,D,A,B
M: A-a, B-b, C-c, D-d.
C-d dissatisfied couple.
Unstable marriage:
y
X
X
Y
x
X –y
dissatisfied pair.
y
The proposal Algorithm: “man proposes, women disposes”.
For each currently unattached men X:
X proposes to the most desirable women on his list , who
has not already rejected him.
For each women y:
upon receiving a proposal , decide to accept or to reject.
* If man X proposed to women y, she will accept the proposal if she is currently
unmarried, or if her current mate Y is less desirable to her than X.(poor Y reverts to the
unmarried state).
* The algorithm repeats this process, terminating when every person has been married.
Algorithm always terminates with a stable marriage.
The algorithm uses
O(n^2)
proposes.
A probabilistic analysis of a deterministic algorithm.
What is the number of the proposes in average case?
Tp -the number of proposals made during the execution.
Assumption: input chosen independently random and uniformly.
We do not assume that the men have chosen their random preference list
in advance.
Each time a man has to make a proposal , he picks a random woman
from the set of women not already propositioned by him.
This is equivalent to choosing the random preference list prior to the execution.
!!!**In this approach we remove the dependence on the history of proposal.