Rumour Spreading. [10 marks total; 5 marks each] There are n people, each in possession of a dierent 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.

(a) 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. (b) 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.)