Please complete Bruteforce.java using the information provided.

Friends.java

import java.util.List; import java.util.ArrayList; public class Friend { String name; List conflicts; public Friend(String name) { this.name = name; this.conflicts = new ArrayList(); } public String toString() { return this.name; } public void setConflicts(List conflicts) { for (Friend friend: conflicts) this.conflicts.add(friend); } public boolean hasConflictWith(Friend friend) { int idx = this.conflicts.indexOf(friend); if (idx >= 0) return true; else return false; } } 

Bruteforce.java

import java.util.List; import java.util.ArrayList; import java.util.Arrays; public class BruteForce { public static void main(String args[]) { testOne(); // testTwo(); } //--------------------------------------------------- // An example, with four friends: Jack, Mary, Henry, and Elizabeth // - Jack has a conflict with Mary and Elizabeth // - Mary has conflict with Henry and Elizabeth // - Henry has a conflict with Elizabeth // There is a single subset of size = 2 having no conflicts: // Jack and Henry public static void testOne() { Friend jack = new Friend("Jack"); Friend mary = new Friend("Mary"); Friend henry = new Friend("Henry"); Friend elizabeth = new Friend("Elizabeth"); Friend[] allFriends = {jack, mary, henry, elizabeth}; Friend[] jack_conflicts = {mary, elizabeth}; jack.setConflicts(new ArrayList(Arrays.asList(jack_conflicts))); Friend[] mary_conflicts = {henry, elizabeth}; mary.setConflicts(new ArrayList(Arrays.asList(mary_conflicts))); Friend[] henry_conflicts = {elizabeth}; henry.setConflicts(new ArrayList(Arrays.asList(henry_conflicts))); List best = optimize(allFriends); System.out.println("largest independent set:"); for (Friend f: best) System.out.print(f + " "); System.out.println(); } //--------------------------------------------------- public static void testTwo() { // implement this List best = optimize(allFriends); System.out.println("largest independent set:"); for (Friend f: best) System.out.print(f + " "); System.out.println(); } //---------------------------------------------------------- public static List optimize(Friend allFriends[]) { // implement this } // optimize() } 

You have ten friends. Some of them have conflicts with each other. You want to invite as many friends as you can to a dinner party, in a way that none of your guests has a conflict with any other guest. We will assume that "has conflict with" is a symmetric relationship: if A has a conflict with B, then B also has a conflict with A. (And no person has a self-conflict.) 1.1 List of friends Here is a table showing your friends and showing which friends have conflicts with other friends: Since the "has conflict with" relation is symmetric, the table itself is symmetric. Find the maximal independent set: the largest set of friends such that no friend in the set has a conflict with any other friend in the set. I've created infrastructure for you, in the BruteForce folder of the course gitlab: BruteForce.java and Friend.java. Use these. 1.2 Enumerating subsets Here's an easy way to enumerate all of the subsets of a given set: suppose I have N items in my set. Declare a boolean array choose [] of size N. Then, do the following: for index =0 to 2N1{ for j=0 to N1{ choose [j]= false \} for j=0 to N1{ if bit j of index is set \{ choose [j]= true \} // now, build the ith subset of the friends: // for j in 0 to N-1, include friend j if choose[j] is true // if there are no conflicts among the friends chosen in this set, // then count how many friends are in this set // keep track of the largest subset seen \} Here's how to determine if the ith bit of index is set (0i0, where val =2i. (This is the bitwise AND operator.) So for example, if index \& 1>0, then zeroth bit of index is set. If index \& 64>0, then the six bit of index is set. Again, we are numbering the bits of an N-bit number from 0 to N1. Write this function in Main: List> optimize(Friend[] allFriends) It should return a list consisting of the largest conflict-free subset of friends I can invite to my dinner party. The function testOne() in Main.java shows how to set up a friend group and call optimize(). Write a function testTwo () on Main that sets up the friend group represented by the table above and then calls optimize() to find the largest conflict-free subset