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?