Problem 88

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

# Prisoners regroup

Due: April 26
Points: 5

Problem 69 was about separating $$n$$ prisoners, with $$m$$ pairs of enemies among them, into 2 cells, so that the number of enemy pairs within either cell would be at most $$m/2$$. We saw a deterministic way to do this, and a faster randomized algorithm to do the same thing.

Suppose there are $$k\ge 2$$ cells instead of only just 2 cells.

1. Modify the deterministic algorithm from before to adapt to this new situation. The algorithm will still involve looping through the prisoners and moving them one at a time. The difference is that there are now $$k-1$$ other cells to move each prisoner to.

2. Come up with a new randomized algorithm to solve the prisoners problem with $$k$$ cells. Again, it needn't be very different than the randomized algorithm from before.

3. Compare the running time of these two algorithms.

4. Compare the performance of these two algorithms. How many enemy-pairs will there be within any cell in the worst case for the deterministic algorithm? How many enemy-pairs with there be within any cell in expectaction for the randomized algorithm?