404_Ch5_Lecture - Computer Science
Download
Report
Transcript 404_Ch5_Lecture - Computer Science
UMass Lowell Computer Science 91.404
Analysis of Algorithms
Spring, 2002
Chapter 5 Lecture
Randomized Algorithms
Sections 5.1 – 5.3
source: 91.404 textbook Cormen et al.
The Hiring Problem
Job candidates are numbered 1…n
HIRE-ASSISTANT(n)
best 0
candidate 0 is a least-qualified dummy candidate
for i 1 to n
do interview candidate i
if candidate i is better than candidate best
then best i
hire candidate i
Analysis Goal:
- Analyze interview & hiring cost instead of running time
- Interviewing Cost = ci << Hiring Cost = ch
- Assume m people are hired
- Total Cost: O(nc mc )
i
h
Analyzing the Hiring Problem
Worst-Case Analysis:
Hire every candidate interviewed
How can this occur?
If candidates come in increasing quality order
Hire n times: total hiring cost = O(nch)
Probabilistic Analysis:
Appropriate if information about random distribution of inputs
is known
Use a random variable to represent cost (or run-time)
Find expected (average) cost (or run-time) over all inputs
We’ll use this technique to analyze hiring cost…
First need to introduce indicator random variables to simplify analysis
Indicator Random Variables
Indicator random variable I{A} associated with event A:
if A occurs
1
I { A}
0 if A does not occur
Example: Find expected number of heads when flipping a
fair coin
Sample space S = {H, T }
1 if Y H
Random variable Y takes on values H, T X H I {Y H }
0 if Y T
Prob(H ) = Prob(T ) = 1/2
XH counts number of heads in a single flip
Expected number of heads in a single coin flip = expected value of XH
E[ X H ] E[ I{Y H}] 1 Pr{Y H } 0 Pr{Y T }
1
1 1
1 0
2
2 2
Indicator Random Variables
(continued)
Lemma 5.1: Given sample space S and an event A
in S. Let XA = I{A}. Then E[XA] = Pr{A}.
Proof: By definitions of indicator random variable
and expectation: E[ X ] E[ I{A}]
A
1 Pr{ A} 0 Pr{ A}
Pr{A}
Useful for analyzing sequence of events…
Analyzing the Hiring Problem
using Indicator Random Variables
Assume candidates arrive in random order
X = random variable modeling number of times we hire
difficult
Without indicator
n
calculation
random variables: E[ X ] x Pr( X x) in this case
x 1
With indicator
random variables:
X X1 X 2 X n
if candidate i is hired
1
X i I {candidate i is hired }
0
if
candidate
i
is
not
hired
Need to find this
E[ X i ] Pr{candidate i is hired }
by
Lemma 5.1
Analyzing the Hiring Problem
using Indicator Random Variables
(continued)
HIRE-ASSISTANT(n)
best 0
candidate 0 is a least-qualified dummy candidate
for i 1 to n
do interview candidate i
if candidate i is better than candidate best
then best i
Need to calculate probability
hire candidate i
that these lines are executed
Candidate i is hired when candidate i is better than each of candidates 1…i-1
Randomness assumption: any of first i candidates is equally likely to be bestqualified so far
Candidate i has probability of 1/i of being better than each of candidates 1…i-1
Probability candidate i will be hired is therefore: 1/i
E[ X i ] Pr{candidate i is hired } 1 / i
Analyzing the Hiring Problem
using Indicator Random Variables
(continued)
HIRE-ASSISTANT(n)
best 0
candidate 0 is a least-qualified dummy candidate
for i 1 to n
do interview candidate i
Assuming that
if candidate i is better than candidate best
candidates are presented
then best i
in random order, total
hire candidate i
hiring cost is in O(ch ln n)
n
n
n
i 1
i 1
i 1
E[ X ] E[ X i ] E[ X i ] 1 / i ln n O(1)
X X1 X 2 X n
by
Linearity of
Expectation
E[ X i ] Pr{candidate i is hired } 1 / i
And now for something
different…
Randomized Algorithm:
Put
H
randomness into algorithm itself
Make choices randomly (e.g. using coin flips)
Use pseudorandom-number generator
Algorithm itself behaves randomly
Different from using probabilistic assumptions
about inputs to analyze average-case behavior
of a deterministic (non-random) algorithm
Randomized algorithms are often easy to design
& implement & can be very useful in practice
Randomized Hiring Algorithm
RANDOMIZED-HIRE-ASSISTANT(n)
random
randomly permute the list of candidates
best 0
candidate 0 is a least-qualified dummy candidate
for i 1 to n
do interview candidate i
if candidate i is better than candidate best
deterministic
then best i
hire candidate i
Represent an input using candidate ranks:
rank (1), rank (2), , rank (n)
Randomly permuting candidate list creates a random list of candidate ranks.
The expected cost of RANDOMIZED-HIRE-ASSISTANT is in O(ch ln n).
Note: We no longer need to assume that candidates are presented in random order!
Nothing is ever really free…
RANDOMIZED-HIRE-ASSISTANT(n)
randomly permute the list of candidates
best 0
candidate 0 is a least-qualified dummy candidate
How do we for i 1 to n
do this well?
do interview candidate i
How much
if candidate i is better than candidate best
time does it
take?
then best i
hire candidate i
Goal: permute array A
A rank (1), rank (2), , rank (n)
Approach: assign each element A[ i ] a random priority P[ i ]
Randomized Permutation
Algorithm
Approach: assign each element A[ i ] a random priority P[ i ]
PERMUTE-BY-SORTING(A)
n length[A]
for i 1 to n
do P[ i ] RANDOM(1,n3)
sort A, using P as sort keys
return A
This step dominates the
running time. It takes
W(n lg n) time if pairs of
values are compared while
sorting
Choose a random
number between 1
and n3
(makes it more likely
that all priorities are
unique)
Now we need to show that PERMUTE-BY-SORTING
produces a uniform random permutation of the input,
assuming all priorities are distinct…
Randomized Permutation
Algorithm Analysis
Claim: PERMUTE-BY-SORTING produces a uniform random
permutation of the input, assuming all priorities are distinct.
Proof Sketch: Consider permutation in which each A[ i ] has i th smallest
To show this permutation priority
occurs with probability 1/n! …
Let Xi be event that element A[ i ] receives i th smallest priority.
Probability that, for all i, event Xi occurs is :
Pr{ X 1 X 2 X 3 X n1 X n }
Pr{ X 1} Pr{ X 2 | X 1} Pr{ X 3 | X 2 X 1}Pr{ X n | X n1 X 1}
1 1 1 1 1
Pr{ X 1 X 2 X 3 X n1 X n }
n n 1 2 1 n!
To complete the proof, now apply the argument
above to any fixed permutation of {1,2,…,n}:
(1), (2), , (n)
Randomized Permutation
Algorithm Improvement
RANDOMIZE-IN-PLACE(A)
n length[A]
for i 1 to n
do swap A[ i ]
A[RANDOM(i,n)]
Claim: RANDOMIZE-IN-PLACE produces a uniform random
permutation of the input.
Proof uses a loop invariant for the for loop. See p. 103 of text for detais.