wrote:=20 Hi, There is a link from the class webpage to solutions of last year = exams. Did you try using them? Best, Michael ----- Original Message -----=20 From: Eitan Yanovsky=20 To: elkinm@cs.bgu.ac.il=20 Sent: Wednesday, January 31, 2007 2:42 PM Subject: Question about an exam =20 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 = upwards and it wont resend it again. I dont understand how in the solution you gave, if a path is of = length sqrt(M) and it has sqrt(M) values on the edge of it it will take = o(M) time to detain one value. It seems that it works as a pipeline = converagecast simply with no order in which to send the values. each = round one item will be sent up, then at the worst case the item with the = lowest value will be sent upwards after Sqrt(M) rounds but now it can't = be detailed another Sqrt(M) rounds because all the other items that were = sent upwards before him have already been sent up.=20 It seems like at the worst case, the item with the lowest value = will reach the start of the path after Sqrt(M) rounds. Am I wrong? Thanks Eitan ------=_NextPart_000_0121_01C7455B.F9FDF8A0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

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 = Yanovsky

To: Michael Elkin

Sent: Wednesday, January 31, = 2007 3:01=20 PM

Subject: Re: Question about an = exam

Yes, 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:=20

Hi,

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 = Yanovsky

To: elkinm@cs.bgu.ac.il=20

Sent: Wednesday, January = 31, 2007=20 2:42 PM

Subject: 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--