There are many sunny days in Ithaca, New York; but this year, as it happens, the

Question

There are many sunny days in Ithaca, New York; but this year, as it happens, the spring ROTC picnic at Cornell has fallen on a rainy day. The ranking officer decides to postpone the picnic and must notify everyone by phone. Here is the mechanism she uses to do this.

Each ROTC person on campus except the ranking officer reports to a unique superior officer. Thus the reporting hierarchy can be described by a tree T, rooted at the ranking officer, in which each other node v has a parent node u equal to his or her superior officer. Conversely, we will call v a direct subordinate of u. See Figure 6.30, in which A is the ranking officer, B and D are the direct subordinates of A, and C is the direct subordinate of B.

To notify everyone of the postponement, the ranking officer first calls each of her direct subordinates, one at a time. As soon as each subordinate gets the phone call, he or she must notify each of his or her direct subordinates, one at a time. The process continues this way until everyone has been notified. Note that each person in this process can only call direct subordinates on the phone; for example, in Figure 6.30, A would not be allowed to call C.

We can picture this process as being divided into rounds. In one round, each person who has already learned of the postponement can call one of his or her direct subordinates on the phone. The number of rounds it takes for everyone to be notified depends on the sequence in which each person calls their direct subordinates. For example, in Figure 6.30, it will take only two rounds if A starts by calling B, but it will take three rounds if A starts by calling D.

Give an efficient algorithm that determines the minimum number of rounds needed for everyone to be notified, and outputs a sequence of phone calls that achieves this minimum number of rounds.

A should call B before D. | Figure 6.30 A hierarchy with four people. The fastest broadcast scheme is for A to call B in the first round In the second round, A calls D and B calls C. If A were to call D first, then C could not learn the news until the third round.

Explanation / Answer

Algorithm :

Input : A Tree T, rooted at the ranking officer, in which each other node v has a parent node u equal to his or her superior officer.

Steps:

1. Get count of all descendant of every node of tree T including itself, Initialize maxTimer = 0

2. Now, initialize counter[r] = 0 for root node r add it into a queue q1

3. Pop a node r from queue q1 and add all direct subordinates of node r into a queue q2, sort queue q2 in decreasing order(based on number of decendant calculated in step 1).

4. Pop node n1 from queue q2 and counter[n1] = counter[r]+1, and push node n1 to queue q1

5. Compare counter[n1] with maxTimer and update maxTimer if counter[n1] > maxTimer to maxTimer =counter[n1]

6. Print "Agent "r" called agent "n1" at time counter[q2]"

7. Repeat step 4,5,6,7 till queue q2 becomes empty

6. Repeat step 3,4,5,6,7 till queue q1 becomes empty

7. Minimum number of rounds is maxTimer

Example given in question, we will call A->B as B as 2 number of descendant including itself while D has only 1

so A->B

then B->C and A->D will go parallely

so answer is 2

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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