Generating and proving an Algorithm:

We now revisit the randomized MAXCUT problem presented in class.

In our presentation, we assigned a monkey on every vertex of the input graph G and asked them to each flip a fair coin and determine the vertex is to be put on the left or the right side. We showed that this randomized algorithm achieves a cut size in expectation at least 50% of the maximum possible.

Note that the total number of random choices the monkeys could make collectively is 2n for a graph of n vertices.

Use universal hash function to design an alternative randomized algorithm that also achieves this performance in expectation, furthermore your alternative randomized algorithm has the following advantage: If we tried all possible choices made by your randomized algorithm there are only a polynomial number O(|G|k) (where |G| is the size of G, and k is some constant) of possible choices, and therefore one could try all these choices deterministically and pick the largest cut produced. Show that this gives a deterministic algorithm that runs in time O(|G|k), for some constant k, and achieves a cut size at least 50% of the maximum possible.