Question

Theorem 5.1 Let n measure the size of the input for a certain task, and suppose that any algorithm that solves this task must distinguish between f (n) different pos- sibilities. If an algorithm is based on an operation X that has m different outcomes, then the worst-case number of X operations this algorithm performs must be at least logm(f(n)).

Consider the task of selecting a person at random from a group of n people by repeatedly rolling a single six-sided die.

a) Use Theorem 5.1 to find a lower bound on the worst-case number of rolls needed to select a person from a group of n = 72 people. 

b) Describe an optimal algorithm for selecting a person from a group of n = 72 people.

c) What is the greatest value of n for which a person can be selected at random using five rolls?

Answer 1

Part(a)

Number of people, n = 72

Since we are using a six-sided die, m = 6

Since we need to distinguish between n people, f(n) = n

Thus, by theorem 5.1, lower bound on the worst-case number of rolls = log6(f(72)) = log6(72) = 2.38685

Thus, we need atleast 3 rolls.

Part(b)

The algorithm is as follows:

1) Divide the group into 6 smaller groups of 12 people each and map each group to a number on the die.

2) Roll the die and select the group with the number that appears on the die.

3)Now, divide that group of 12 people into six smaller groups of 2 people each. Map each group to a number on the die.

4) Roll the die again and select the group with the number that appears on the die.

5) Roll the die again. If the number is odd then select the first person, if it is even then select the second person from the group of 2 people.

Doing so we will select a random person from a group of 72 people using 3 rolls of the die. Thus, this is an optimal algorithm.

Part (c)

Let the number of die rolls be r in the worst case.

Then from Theorem 5.1,

Thus,

Thus, the maximum value of n for 5 rolls of a die is 7776.