Hi again,

A simpler solution: =
consider a path=20
v0,v1,...,v_{k}, with v0 being the root.

Initial distribution of items is v_k =
keeps=20
{1,2,..,k},

v_{k-1} keeps {k+1,k+2,..,2k}, =
...,

v1 keeps=20
{k(k-1)+1,...,k(k-1)+k}.

After k rounds this all shifts by 1 =
(assuming that=20
the largest among k smallest items is sent):

v_{k-1} keeps {1,2,..,k},=20

v_{k-2} keeps {k+1,k+2,..,2k},=20
...,

v1 keeps=20
{k(k-2)+1,...,k(k-2)+k}.

Hence the root learns {1,2,..,k} after k^2 rounds.

Rad =3D k, Time =3D k^2.

Best,

Michael

----- Original Message -----From:=20 Eitan = YanovskyTo:Michael ElkinSent:Wednesday, January 31, = 2007 3:01=20 PMSubject:Re: Question about an = examYes, my question is about the solution.The explanation there states what I've written and it seems wrong = to=20 me.

On 1/31/07,Michael=20 Elkin<elkinm@cs.bgu.ac.il>=20 wrote:=20Hi,There is a link from = the class=20 webpage to solutions of last year exams. Did you try using=20 them?Best,Michael----- Original Message ----- =From:= Eitan = YanovskyTo:elkinm@cs.bgu.ac.il=20Sent:Wednesday, January = 31, 2007=20 2:42 PMSubject:Question about an = exam

Hello,I've got a question about Moed a of 2005 question 3 section = b.The algorithm that is stated there sends on each round a = number=20 upwards and it wont resend it again.I dont understand how in the solution you gave, if a path is = of=20 length sqrt(M) and it has sqrt(M) values on the edge of it it will = take=20 o(M) time to detain one value. It seems that it works as a = pipeline=20 converagecast simply with no order in which to send the values. = each round=20 one item will be sent up, then at the worst case the item with the = lowest=20 value will be sent upwards after Sqrt(M) rounds but now it can't = be=20 detailed another Sqrt(M) rounds because all the other items that = were sent=20 upwards before him have already been sent up.It seems like at the worst case, the item with the lowest = value will=20 reach the start of the path after Sqrt(M) rounds.Am I wrong?Thanks=Eitan

------=_NextPart_000_0121_01C7455B.F9FDF8A0--