Greedy implementation

Question

You know who knows who among the Russian people you would like to visit at the party. Suppose you “know” symmetrically: if I know you, you know me. You have additional requirements for each person to have at least 5 new people to meet at the party, and therefore, no one feels too isolated, each person should know at least 5 people at the party. Your initial list may not satisfy these additional two conditions, so you may need to exclude some people from the invitation list (or perhaps you cannot have a party at all with these restrictions). Find the largest possible subset of Russian people whom you can invite and who satisfy two other requirements. For the main task, find the O (n ^ 3) algorithm and explain its order and its logic.

I ask you not to answer, but for guidance on where to start.

Answer 1

Sounds good for applying a graph algorithm.

Create a schedule of people, G For n people, there will be n nodes on the graph. Connect nodes i and j if person i knows person j .

Let the first iteration of G be called G_0 . Get G_1 by going through G and eliminate any person who knows too many or too few people. (That is, exclude person i if the number of links to i is < 5 or > n-5 .)

Repeat the process, getting G_2 , G_3 to the maximum of n (or so) iterations, getting G_n . The people remaining on this graph are the people you should invite.

Each of the n passes requires checking n people against n other people, so the algorithm is O(n^3) .

---

MATLAB code for this (you did not ask for it, but I thought it was interesting and still written):

 % number of people on original list N = 10 % number of connections to (attempt) to generate % may include self-links (i,i) or duplicates M = 40 % threshold for "too few" friends p = 3 % threshold for "too many" friends q = 3 % Generate connections at random G = zeros(N); for k = 1:M i = randi(N); j = randi(N); G(i,j) = 1; G(j,i) = 1; end % define people to not be their own friends for i = 1:N G(i,i) = 0; end % make a copy for future comparison to final G G_orig = G % '1' means invited, '0' means not invited invited = ones(1,N); % make N passes over graph for k = 1:N % number of people still on the candidate list n = sum(invited); % inspect the i'th person for i = 1:N people_known = sum(G(i,:)); if invited(i) == 1 && ((people_known < p) || (people_known > nq)) fprintf('Person %i was eliminated. (He knew %i of the %i invitees.)\n',i,people_known,n); invited(i) = 0; G(i,:) = zeros(1,N); G(:,i) = zeros(1,N); end end end fprintf('\n\nFinal connection graph') G disp 'People to invite:' invited disp 'Total invitees:' n 

Output example (10 people, 40 connections, at least 3 people should know, at least 3 people should not know)

 G_orig = 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 Person 2 was eliminated. (He knew 2 of the 10 invitees.) Person 7 was eliminated. (He knew 2 of the 10 invitees.) Final connection graph G = 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 People to invite: invited = 1 0 1 1 1 1 0 1 1 1 Total invitees: n = 8 

Answer 2

I assume the following data structure for representing information:

 Person name : string, if this is empty or null, the person isnt not invited to party knows: array of pointers to type Person. Indicates whom this person 'knows' knows_cnt : size of "knows" array 

Information about everyone (including the host) can be stored in the "Personal Identities [n]" section.

The leading side is in the first position.

The routine that may be needed for algo:

 RemovePerson (individuals, n, i) // removes i'th person from individuals an array of n persons set individuals[i].name to empty so that this person is discarded For j from 1 to individuals[i].knows_cnt // as knows is symmetric, we can get the persons' contact right away Person contact = individuals[i].knows[j] if contact.name is empty, continue modify contact.knows to remove i'th person. modify corresponding contact.knows_cnt end for end RemovePerson 

Suggested Algorithm:

 change = true invitees = n while [change == true] change = false for i = 2 to n do // start from 2 to prevent the host getting discarded due to condition #2 if individuals[i].name is empty, continue // condition #1, // check if the person knows atleast 5 people if individuals[i].knows_cnt < 5 change = true invitees = invitees - 1 RemovePerson(individuals, n, i) // condition #2 // check to find out if the person will get to know 5 new people if (invitees - individuals[i].knows_cnt) < 5 change = true invitees = invitees - 1 RemovePerson(individuals, n, i) end for end while return invitees 

Let me know if you encounter any difficulty in understanding this algorithm.