Please use Java and add comments for my understanding. Please don't copy and paste from old/similar answers - Clear instructions are provided. Thanks!

1.3

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

//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() } ---------------------------------------------------------------------------------------------------------------------------------------------

//Friend.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; } } 

1 Independent Sets 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 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 \{ 1 choose [j]= true \} // now, build the ith subset of the friends: // for j in 0 to N1, 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=2. (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. Graduate students, and undergraduates who would like a little extra credit: create an array of boolean arrays, sorted in descending fashion by the number of true values in each boolean array. Then, you can stop checking after the first independent set you find