There is a group of n people, some of them know each other. One of the people he

Question

There is a group of n people, some of them know each other. One of the people heard a rumor, that he/she can secretly tell just to l person he/she knows. That person, in turn, can tell a rumor to other person and so on. If the person hear the rumor that he/she already know, this person will now share it with anyone else (assuming that if he/she heard than everybody knows it. You need to find out, is it possible that eventually everybody will hear the rumor? Represent this problem as one of the algorithmic problems that we studied in our class. What is this algorithmic problem? Is it possible to solve it in a polynomial time?

Explanation / Answer

Solution:

The pattern goes like this, a person hear about the rumor and share it with another person then stops and the other person does the same and the process goes on. So, the question is when the person who already knows about the rumor here about it again, should we consider that everybody knows about the rumor,

No, we cannot do that, That doesn't justify that everyone know about the rumor. Let me explain why,

Suppose 20 people are there in the party and one get to know about the rumor, then he share the rumor with another person, that another person share the rumor with other and they keep on sharing this interesting rumor till 10 people have already knew about the rumor. Since one person is restricted to telling just 1 person. The 10th one decided to tell about the rumor to the first person. Now, if we consider that everybody knows about the rumor we are wrong. What about other 10 people ?

As far as algorithmic point of view is concerned, We can see this problem as search problem and BFS or DFS may be useful here which can solve this in polynomial time. DFS will be more helpful in finding the cycle.

So two things can be done here, if we are assuming that the person heard the rumor twice then everybody knows about it, then we need to just find a cycle in the graph, where people will acts as a node. another one is my point of view which will give exact solution where we will treat people as nodes but we will check if the rumor has visited all the people in the group.

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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