Transcript ppt

Probabilistic algorithms
Sometimes it is preferable to choose a course
at random, rather than spend time working
out which alternative is best.
Main characteristic
The same algorithm may behave differently
when it is applied twice to the same
instance.
Prabhas Chongstitvatana
1
Probabilistic != Uncertain
Paradox :
The error probability can often be brought down
below that of a hardware error during the
significantly larger time needed to compute the
answer deterministically.
Prabhas Chongstitvatana
2
There are problems for which no
algorithm is know, be deterministic or
probabilistic, that can give the answer
with certainty within a reasonable amount
of time, yet probabilistic algorithm can
solve the problem quickly if an arbitrarily
small error probability is tolerated.
Example : determine whether a 1000 digit
number is prime or composite.
Prabhas Chongstitvatana
3
Type of probabilistic algorithms
Numerical
Confidence
interval
More time =
more precise
Monte Carlo
Exact but
More time = less
sometimes wrong error probability
Las Vegas
Always correct
If soln can be
but sometimes no verified
answer
efficiently
Answer with confidence interval : “with
probability 90% the answer is 59 plus or minus 3”
Prabhas Chongstitvatana
4
Expected vs average time
deterministic
probabilistic
Average time
The average time taken
by an algorithm when
each possible instance of
a given size is equally
likely.
Expected time The mean time that it
would take to solve the
same instance over and
over.
Prabhas Chongstitvatana
5
Worst-case expected time
Expected time taken by the worst possible
instance of a given size.
Example
Las Vegas can be more efficient than
deterministic one but only with respect to
expected time. (if bad luck, LA takes long time)
Quicksort deterministic worst-case (n 2 )
Quicksort probabilistic
O(n log n)
Prabhas Chongstitvatana
6
QuicksortLV( T[i..j] )
If j-i is sufficiently small then insertsort( T[i..j] )
else
p = T[uniform(i..j) ]
pivotbis(T[i..j],p,k,l)
quicksortLV(T[i..k])
quicksortLV(T[l..j])
Pivotbis(T[i..j], p, k, l) partitions T into three sections,
p as pivot. After pivoting the elements in T[i..k] < p,
T[k+1.. l-1] = p and T[l..j] > p. Return k,l.
Prabhas Chongstitvatana
7