Rumor spreading There are n people, each in possession of a different rumor. The

Question

Rumor spreading There are n people, each in possession of a different rumor. They want to share all the rumors with each other by sending electronic messages. Assume that a sender includes all the rumors he or she knows at the time the message is sent and that a message may only have one addressee.

Design a greedy algorithm that always yields the minimum number of messages they need to send to guarantee that every one of them gets all the rumors.

Question directly copied from the textbook. Any so-called expert could answer this. As a student, I have come up with an answer and want to compare to someone else's answer. This can easily be answered and absolutely does not need any other context.

Explanation / Answer

I think the answer is 2n-2,

one way to reach this solution is :

suppose n-1 person share their rumor with one designated person and then that designated person, after collecting all rumors along with his rumor, communicate with rest n-1 persons. and thus in n-1 +n-1 time, all rumors will be shared.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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