Graded Problem (Page limit: 1 sheet; 2 sides) 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 2" 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 algorithmn 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 0(Gk), for some constant k, and achieves a cut size at least 50% of the maximum possible. Graded Problem (Page limit: 1 sheet; 2 sides) 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 2" 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 algorithmn 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 0(Gk), for some constant k, and achieves a cut size at least 50% of the maximum possible