This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
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.
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.
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.
Compare the running time of these two algorithms.
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?