Problem 80

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Analysis of prisoners algorithm

Due: April 19
Points: 4

Problem 69 presents a problem of grouping $$n$$ prisoners into 2 cells, where there are $$m$$ pairs of prisoners that don't get along and should not be grouped together.

We saw that a clever deterministic algorithm guarantees that the number of pairs of enemies that are not in the same cell together is at least $$\frac{m}{2}$$.

Here is a rather un-clever randomized solution: For each of the $$n$$ prisoners, flip a coin to determine which cell they go into, randomly. So each prisoner ends up in one cell with probability $$\frac{1}{2}$$, or the other cell with probability $$\frac{1}{2}$$.

Complete the end of Problem 69 for this algorithm:

1. Explain why the number of enemies within either cell will be at most $$m/2$$, on average, after running your algorithm.
2. Analyze the worst-case big-O running time of your algorithm.

Hint: for (2), consider each of the $$m$$ enemy pairs individually. What is the probability that that pair is in the same cell or in two different cells?