A group of n guests shows up to a house for a party, and any two guests are either friends or enemies. There are two rooms in the house, and the host wants to distribute guests among the rooms, breaking up as many pairs of enemies as possible. The guests are all waiting outside the house and are impatient to get in, so the host needs to assign them to the two rooms quickly, even if this means that its not the best possible solution. Come up with an efficient algorithm that breaks up at least half the number of pairs of enemies as the best possible solution, and prove your answer.

(a)We constructed a greedy 1/2-approximation algorithm for this problem that runs in time O(V +E) prior. Now give a randomized algorithm that achieves (in expectation) the same approximation guarantee in time O(V ).

(b) Your solution in part (a) probably had to flip O(V ) random coins, but coins are expensive, use hashing to give an algorithm that only flips O(logV) random coins.