Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.

For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.

Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.


Andrei

If every superior uses a conference call to talk to his subordinates, then the news propagates exactly proportional to the depth of the heirarchy.

:)

Of course, if he has to call all of his subordinates in sequence, then things are different...but in that case, we need a measurement for "fast."  Are we looking for an algorithm that provides the lowest possible maximum time, lowest average, or something else?

Andrei Alexandrescu wrote:
> Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.
> 
> For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.
> 
> Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.
> 
> 
> Andrei

Russell Lewis wrote:
> If every superior uses a conference call to talk to his subordinates, then the news propagates exactly proportional to the depth of the heirarchy.
> 
> :)
> 
> Of course, if he has to call all of his subordinates in sequence, then things are different...but in that case, we need a measurement for "fast."  Are we looking for an algorithm that provides the lowest possible maximum time, lowest average, or something else?

Time from the president lifting the phone to the time the last private hears it.

Andrei

Andrei Alexandrescu wrote:
> Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.
> 
> For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.
> 
> Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.
> 
> 
> Andrei

Hm, just call every subordinate you have? You need to tell everyone anyway.

I can't figure out the problem.

"Russell Lewis" <webmaster@villagersonline.com> wrote in message news:gd07kk$28nu$1@digitalmars.com...
> If every superior uses a conference call to talk to his subordinates, then the news propagates exactly proportional to the depth of the heirarchy.
>
> :)
>

Yea, but what's the overhead for arranging to get everyone in on the conference call at the same time? :)

-3.2 seconds.  It will be on the Drudge Report before the president picks up the phone.

Seriously, though, the algorithm is as follows:

- Give each private a "cost" of 0, since he has no calls to make
- Iterate through the list of superiors, starting with the lowest
  level and working upwards:
  - Sort the superior's subordinates by their cost, from greatest
    cost to least.
  - The superior will plan to call his subordinates in this order
  - The "cost" of the superior is equal to
       max (over subordinates si) i + cost(si)
    That is, each term in the max() is teh cost of the subordinate,
    plus his order in the list.  The total cost of this superior is
    the time from when he makes his first call, until the last
    private in his tree is notified.

This works because of two points:
1) The cost of a given officer notifying his tree doesn't depend on
   his upper heirarchy.  Thus, we can build the values from bottom up.
2) If an officer calls any high-cost subordinate after any lower-cost
   subordinate, then that obviously will make the tree finish later
   than in my suggested order.

Russ

Andrei Alexandrescu wrote:
> Russell Lewis wrote:
>> If every superior uses a conference call to talk to his subordinates, then the news propagates exactly proportional to the depth of the heirarchy.
>>
>> :)
>>
>> Of course, if he has to call all of his subordinates in sequence, then things are different...but in that case, we need a measurement for "fast."  Are we looking for an algorithm that provides the lowest possible maximum time, lowest average, or something else?
> 
> Time from the president lifting the phone to the time the last private hears it.
> 
> Andrei
> 

"Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:gd078s$284f$1@digitalmars.com...
> Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.
>
> For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.
>
> Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.
>

The problem can be thought of as running on a multicore machine with one separate core assigned to each person. Ie, every member of the military can all be doing independant actions simultaniously. Of course, the actual phone call prevents the people involved in the call from doing other things at the same time: unless they each have two phone lines and are really good multitaskers, but I'm going to assume that's not true in the general case (or the liutenant case, or the private case, etc ;) ).

I'm also going to ignore the case where a person is in the same room with one or more of their subordinates, because that would require enough knowledge of the mlitary to know how likely that is to occur at each level of the hierarchy. And I don't know that much about the military ;).

Whenever a person has subordinates left to call, they're doing nothing but calling their subordinates, because that news would be too significant to be wasting time taking a restroom or lunch break ;)

Assume N levels of hierarchy (again because I don't know that much about the military ;) ).

A person at level n has M direct subordinates, and calls each in sequence. With the obvious exception of m[0], m[x] will be receiving the message at the same time m[x-1] is calling their first subordinate. The message is trivial enough, and military people are assumed to be disciplined enough, that we can assume each instance of informing a subordinate takes the same amount of time across the board.

class MilitaryPerson
{
    MilitaryPerson[] subordinates;
    ProcessingCore core;
    bool gotMsg = false;

    void inform()
    {
        receiveMsg();
        hangUpPhone();

        // We can inform our subordinates
        // while our commanding officer
        // informs the rest of our "sibling"
        // comrades in the parent process.
        core.perform(
        {
            foreach(auto sub; iteratorDecreasingNumSubSubordinates)
                sub.inform();
        });
    }

    void receiveMsg()
    {
        gotMsg = true;
    }

    // The purpose of using this type of ordering
    // is to maximize simultaneous core utilization
    MilitaryPerson iteratorDecreasingNumSubSubordinates()
    {
        bool done = false;
        while(!done)
        {
            int maxSub = 0;
            bool found = false;
            MilitaryPerson nextToRet;
            foreach(int i, MilitaryPerson sub; subordinates)
            {
                if(!sub.gotMsg && sub.subordinates.length > maxSub)
                {
                    maxSub = sub.subordinates.length;
                    nextToRet = sub;
                    found = true;
                }
            }

            if(found)
                yield nextToRet; // C#-style
            else
                done = true;
        }
    }
}

On Mon, 13 Oct 2008 14:24:14 -0500, Andrei Alexandrescu wrote:

> Suppose that a miracle happen and the decision is taken at the highest level to retreat all of US military presence from Iraq. That will take a while, but sending the orders quickly is a must.
> 
> For utmost certainty, all orders are to be sent via phone and down the command chain, and only to direct subordinates. Each officer has a variable number of subordinates. Initially the president calls his immediate subordinates, who call their immediate subordinates, etc. Each call can be assumed to take the same amount of time.
> 
> Devise an algorithm that ensures every foot soldier gets the news as quickly as possible, show it is correct, and show it is fast.

But wouldn't this be broadcast on al Jazzera before the generals get the "official" news?

-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell

Reply to Andrei,

> Suppose that a miracle happen and the decision is taken at the highest
> level to retreat all of US military presence from Iraq. That will take
> a while, but sending the orders quickly is a must.
> 
> For utmost certainty, all orders are to be sent via phone and down the
> command chain, and only to direct subordinates. Each officer has a
> variable number of subordinates. Initially the president calls his
> immediate subordinates, who call their immediate subordinates, etc.
> Each call can be assumed to take the same amount of time.
> 
> Devise an algorithm that ensures every foot soldier gets the news as
> quickly as possible, show it is correct, and show it is fast.
> 
> Andrei
> 

Sort everyone under you (directly or indirectly) by the number of subordinates they have. Pick the subordinate with the most subordinates and call the next man in line to them. remove every subordinate down that chain of command and repeat.

This assumes that the depth of command is more or less the same across the board.

Reply to KennyTM~,

> Andrei Alexandrescu wrote:
> 
>> Suppose that a miracle happen and the decision is taken at the
>> highest level to retreat all of US military presence from Iraq. That
>> will take a while, but sending the orders quickly is a must.
>> 
>> For utmost certainty, all orders are to be sent via phone and down
>> the command chain, and only to direct subordinates. Each officer has
>> a variable number of subordinates. Initially the president calls his
>> immediate subordinates, who call their immediate subordinates, etc.
>> Each call can be assumed to take the same amount of time.
>> 
>> Devise an algorithm that ensures every foot soldier gets the news as
>> quickly as possible, show it is correct, and show it is fast.
>> 
>> Andrei
>> 
> Hm, just call every subordinate you have? You need to tell everyone
> anyway.
> 
> I can't figure out the problem.
> 

who do you call first?