3. [10 marks] There are N teams in the local cricket competition and you happen

Question

3. [10 marks] There are N teams in the local cricket competition and you happen to have N friends that keenly follow it. Each friend supports some subset (possibly all, or none) of the N teams. Not being the sporty type but wanting to fit in nonetheless you must decide for yourself some subset of teams (possibly all, or none) to support. You don't want to be branded a copycat, so your subset must not be identical to anyone else's. The trouble is, you don't know which friends support which teams, so you can ask your friends some questions of the form "Does friend A support team B?" (you choose A and B before asking each question). Design an algorithm that determines a suitable subset of teams for you to support and asks as few questions as possible in doing so. 2

Explanation / Answer

The question wants us to design an algorithm to find a unique subset of teams for us to follow which is not followed by our friends. Two subsets are different and unique if any one of them has atleast one team which other don't have.

Ex. {a,b,c,d,e} and {a,b,c,d} are unique because first subset has e which is not present in second one.

Now, let's find out the solution to perform the task.

The Worst Solution:

The worst solution of the problem will be to ask each friend about each team whether they follow it or not? and accordingly choose a subset which is unique but let's look at number of questions asked in this process.

There are N friends and for each Friend we ask a question about each team, i.e. N questions per friend. That means we have to ask n2 questions in this case. O(n2) solution.

Efficient Solution

First, pick up a friend who follows most number of teams. If he follows all the teams then pick the second most teams follower and so on. Now, we ask this friend N questions (1 for each team) and we write down the team names which he doesn't follow. Now for every friend we ask the question about only these teams which we have written down. If a person doesn't follow any one of the team in our written list then we leave him there only and ask no more question to him, move to the next candidate. Because if he doesn't follow this team then our subset is different from his. If a friend follows all the teams included in our list then ask him about the teams which are not in our list. If he follows some other teams also then we are still safe to choose that subset. But if he doesn't follow any other more teams then we have to either add or remove a team in our subset and repeat the process again for each friend. Finally the subset satisfying uniqueness with all friends will be our answer.

This may seem to you more complex but actually it is lot better than O(n2) complexity. For some friends we may even ask one question only if they don't follow at least one team from our list.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.