View mode: basic / threaded / horizontal-split · Log in · Help
October 13, 2008
[OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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.
October 13, 2008
Re: [OT] Retreating from Iraq
"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? :)
October 13, 2008
Re: [OT] Retreating from Iraq
-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
>
October 13, 2008
Re: [OT] Retreating from Iraq
"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;
       }
   }
}
October 13, 2008
Re: [OT] Retreating from Iraq
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
October 13, 2008
Re: [OT] Retreating from Iraq
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.
October 13, 2008
Re: [OT] Retreating from Iraq
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?
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home