Rumour Spreading. [10 marks total; 5 marks each] There are n people, each in pos
ID: 3694152 • Letter: R
Question
Rumour Spreading. [10 marks total; 5 marks each] There are n people, each in possession of a different rumour. They want to share all the rumours with each other by sending messages by e-mail. Assume that a sender includes all the rumours he or she knows at the time the e-mail message is sent, and that an e-mail message may only have one addressee. Give pseudocode for a greedy algorithm to solve the rumour spreading problem that always sends the minimum number of e-mail messages needed to guarantee that everyone gets all the rumours. How many e-mail messages are required to spread the rumours? (Do not express your answer in O() notation; give it exactly in terms of n.)Explanation / Answer
Description of pseudo code:
First guy will send the email to the next guy.
now next guy will be having the rumours(previous guy's all rumours + his rumours)
now he will pass this email to the next guy.
and go on till the last guy.
last guy will send the emails to each of the guy in the group.
Lets understand it by an example.
lets say that there are n =4 people
A B C # totalEmailsSsent
1 1 1 1 // initial rumour count as each one has his own rumour 1
1 2 1 1 // A sends email to B. now B has two rumours(A's,B's) with him. 2
1 2 3 1 // now B send email to C. now C has three rumours(A's,B's,C's) with him 3
1 2 3 4 // now C send email to D. now D has four rumours(A's,B's,C's,D's) with him 4
4 4 4 4 // Now D will send the email to everyone rest (3 of them) 4+(1+1+1)
count =0;
for(int i=1;i<n;i++){ // each person is just passing the information to the next guy
count++;
}
count += (n-1); // last person is just sending emails to everyone rest so n-1 guys => n-1 emails
Part(2). EmailsRequired would be = (n-1) + (n-1) = 2*(n-1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.