A cut is a partition of the vertex set into two sets A, B. We want to maximize the number of edges between A and B (called the " max cut"). Write a java program to generate a random graph of 20 vertices. Use an adjacency matrix. Implement at least two different algorithms for this:

a) Random: choose A and B randomly. (You may wish to make two random choices and choose the best) b) Optimal: use brute force to find the optimal solution. This is done by trying all possible sets A and B and choosing the ones that give the maximum cut.

Test on a good number randomly generated graphs with between 10 and 30 vertices of varying density (by density, we mean the % of possible edges, this parameter should be part of the input). Report both the size of the cut that each algorithm finds as well as the computation time.