Yioop - PHP Search Engine

Feb 28 In-Class Exercise Thread.

Post your solutions to the Feb 28 In-Class Exercise to this thread.

Best,

Chris

Post your solutions to the Feb 28 In-Class Exercise to this thread. Best, Chris

-- Feb 28 In-Class Exercise Thread

init registers C[0]=0 C[1]=0

Step-0 init local variable B[0]=0 B[1]=0

Step-1 read current register and obtain R[] R[0]=0 R[1]=0

Step-2 case c) Since (R[i] !=#) & (R[i]=0 and B[i]!=1).

We assign unbiased random bit to B[i] for our example, let B[0] = 0, B[1] = 1

we write B[i] to current register, C[0]=0 C[1]=1

Step-3 exchange C[0] and C[1] now C[0]=1 C[1]=0

——————————————

Step-1 Read register and obtain bit R[i] R[0]=1 R[1]=0

Step-2 we observe case b for processor i=1 since, R[1]=0 and B[1]=1 we write # to C[1] and halt

Final :

C=[1, #]

(Edited: 2018-02-28)

init registers C[0]=0 C[1]=0 '''Step-0''' init local variable B[0]=0 B[1]=0 '''Step-1''' read current register and obtain R[] R[0]=0 R[1]=0 '''Step-2''' case c) Since (R[i] !=#) & (R[i]=0 and B[i]!=1). We assign unbiased random bit to B[i] for our example, let B[0] = 0, B[1] = 1 we write B[i] to current register, C[0]=0 C[1]=1 '''Step-3''' exchange C[0] and C[1] now C[0]=1 C[1]=0 —————————————— '''Step-1''' Read register and obtain bit R[i] R[0]=1 R[1]=0 '''Step-2''' we observe case b for processor i=1 since, R[1]=0 and B[1]=1 we write # to C[1] and halt '''Final''': C=[1, #]

-- Feb 28 In-Class Exercise Thread

 Initialize: C[0], C[1] = 0, 0
 
 1st iteration	
 P[0]
 Step 0: B[0] = 0
 Step 1: Read Register C[0], fetch R[0]
 Step 2c: Now (R[0] = 0 and B[0] = 0)
      ->    B[0] = Random(0,1)    // o/p is 0
      ->    Write B[0] -> R[0] in C[0] // C[0] is 0
 Step 3: Once P[1] completes step 2, P[0] Exchange register with P[1]

 P[1]
 Step 0: B[1] = 0
 Step 1: Read Register C[1], fetch R[1]
 Step 2c: Now (R[1] = 0 and B[1] = 0)
      ->    B[1] = Random(0,1)    // o/p is 0
      ->    Write B[1] -> R[1] in C[1]
 Step 3: P[1] Exchange register with P[0]

 2nd Iteration	
 P[0]
 Step 1: Read Register C[1], fetch R[1]
 Step 2c: Now (R[1] = 0 and B[0] = 0)
      ->    B[0] = Random(0,1)    //o/p is 1
      ->    Write B[0] -> R[1] in C[1]
 Step 3: Once P[1] completes step 2, P[0] Exchange register with P[1]

 P[1]
 Step 1: Read Register C[0], fetch R[0]
 Step 2c: Now (R[0] = 0 and B[1] = 0)
      ->    B[1] = Random(0,1)    //o/p is 0
      ->    Write B[1] -> R[0] in C[0]
 Step 3: P[0] Exchange register with P[1]
 
 3rd Iteration

 P[0]
 Step 1: Read Register C[0], fetch R[0]
 Step 2b: Now (R[0] = 0 and B[0] = 1)
      ->     write C[0] = #
      ->     Halt
 p[1]
 Step 1: Read Register C[1], fetch R[1]
 Step 2c: Now (R[1] = 1 and B[1] = 0)
      ->    B[1] = Random(0,1)    //o/p is 1
      ->    Write B[1] -> R[1] in C[1]
 Step 3: P[1] exchange register with P[0]

 Final	: C[0] has #

(Edited: 2018-02-28)

Initialize: C[0], C[1] = 0, 0 '''1st iteration''' P[0] Step 0: B[0] = 0 Step 1: Read Register C[0], fetch R[0] Step 2c: Now (R[0] = 0 and B[0] = 0) -> B[0] = Random(0,1) // o/p is 0 -> Write B[0] -> R[0] in C[0] // C[0] is 0 Step 3: Once P[1] completes step 2, P[0] Exchange register with P[1] P[1] Step 0: B[1] = 0 Step 1: Read Register C[1], fetch R[1] Step 2c: Now (R[1] = 0 and B[1] = 0) -> B[1] = Random(0,1) // o/p is 0 -> Write B[1] -> R[1] in C[1] Step 3: P[1] Exchange register with P[0] '''2nd Iteration''' P[0] Step 1: Read Register C[1], fetch R[1] Step 2c: Now (R[1] = 0 and B[0] = 0) -> B[0] = Random(0,1) //o/p is 1 -> Write B[0] -> R[1] in C[1] Step 3: Once P[1] completes step 2, P[0] Exchange register with P[1] P[1] Step 1: Read Register C[0], fetch R[0] Step 2c: Now (R[0] = 0 and B[1] = 0) -> B[1] = Random(0,1) //o/p is 0 -> Write B[1] -> R[0] in C[0] Step 3: P[0] Exchange register with P[1] '''3rd Iteration''' P[0] Step 1: Read Register C[0], fetch R[0] Step 2b: Now (R[0] = 0 and B[0] = 1) -> write C[0] = # -> Halt p[1] Step 1: Read Register C[1], fetch R[1] Step 2c: Now (R[1] = 1 and B[1] = 0) -> B[1] = Random(0,1) //o/p is 1 -> Write B[1] -> R[1] in C[1] Step 3: P[1] exchange register with P[0] '''Final''': C[0] has #

-- Feb 28 In-Class Exercise Thread

 C[0], C[1] = 0
 P[0] is reading C[0], and B[0] = 0
 P[1] is reading C[1], and B[1] = 0
 P[0] sets R[0] to C[0] => 0
 P[1] sets R[1] to C[1] => 0

 Both processors are in case C
 P[0] flips coin and gets 0 => B[0] = 0, R[0] = 0
 P[1] flips coin and gets 1 => B[1] = 1, R[1] = 1

 swap R[0] with R[1]

 P[0] reads R[0], B[0] = 0
 P[1] reads R[1], B[1] = 1

 P[1] finds that R[1] = 0 and B[1] = 1
 P[1] writes # into C[1] and we are done. I think.

C[0], C[1] = 0 P[0] is reading C[0], and B[0] = 0 P[1] is reading C[1], and B[1] = 0 P[0] sets R[0] to C[0] => 0 P[1] sets R[1] to C[1] => 0 Both processors are in case C P[0] flips coin and gets 0 => B[0] = 0, R[0] = 0 P[1] flips coin and gets 1 => B[1] = 1, R[1] = 1 swap R[0] with R[1] P[0] reads R[0], B[0] = 0 P[1] reads R[1], B[1] = 1 P[1] finds that R[1] = 0 and B[1] = 1 P[1] writes # into C[1] and we are done. I think.

-- Feb 28 In-Class Exercise Thread

Let P[i] denote the processor and C[i] denote its choice. Finally, let B[i] be a value which is local to processor P[i] only.

Input: Registers C[0] and C[1] initialized to 0. Output: Exactly one of the registers has the value #. From this point on:

1.) P[i] is initially scanning the register C[i] and has its local variable B[i] initialized to 0.

2.) We are looking at C[1]. It is the case that neither is R[1] #, nor is R[1], 0 & B[1] is 1. After calling the coin flip algorithm an unbiased random bit is assigned to B[1] (heads is 1 and tails is 0), and B[1] is written into the current register(after the coin flip, we get a value of 1).

3.) At this point, P[1] looks at C[0] and P[0] starts looking at C[1] and thus we will reach the stopping condition.

''Let P[i] denote the processor and C[i] denote its choice. Finally, let B[i] be a value which is local to processor P[i] only.'' Input: Registers C[0] and C[1] initialized to 0. Output: Exactly one of the registers has the value #. From this point on: 1.) P[i] is initially scanning the register C[i] and has its local variable B[i] initialized to 0. 2.) We are looking at C[1]. It is the case that neither is R[1] #, nor is R[1], 0 & B[1] is 1. After calling the coin flip algorithm an unbiased random bit is assigned to B[1] (heads is 1 and tails is 0), and B[1] is written into the current register(after the coin flip, we get a value of 1). 3.) At this point, P[1] looks at C[0] and P[0] starts looking at C[1] and thus we will reach the stopping condition.

-- Feb 28 In-Class Exercise Thread

Set registers C[0] and C[1] to 0

The local variables B[0] and B[1] are initialised to 0

The current register is read R[0] and R[1]

R[0] ! = # , R[0] == 0 but B[0] isn't so case C

B[0] = 0 ......similarly..... B[1] = 1

Exchange P[0] = 1 and P[1] = 0

Reading R[0] = 1 and R[1] = 0

for processor 1, R[1] = 0 and B[1] = 1, case 2 => C[1] = #

The C's of the processor C[0] = 1, C[1] = #

Set registers C[0] and C[1] to 0 The local variables B[0] and B[1] are initialised to 0 The current register is read R[0] and R[1] R[0] ! = # , R[0] == 0 but B[0] isn't so case C B[0] = 0 ......similarly..... B[1] = 1 Exchange P[0] = 1 and P[1] = 0 Reading R[0] = 1 and R[1] = 0 for processor 1, R[1] = 0 and B[1] = 1, case 2 => C[1] = # The C's of the processor C[0] = 1, C[1] = #

-- Feb 28 In-Class Exercise Thread

Name : Kunal Deshmukh

Iteration - 1

Input: Registers C[0] and C[1] initialized to 0. Output: Exactly one of the register has the value #. 0 P[i] is initially scanning the register C[i] and

  has its local variable B[i] initialized to 0.

1 Read the current register and obtain a bit R[i]. Hence R[i] is now 0 2 Select one of three cases:

   (a) case [R[i] = #]: halt; -- False
   (b) case [R[i] = 0, B[i] = 1]: write # into the current register and halt; -- False
   (c) case [otherwise]: flip a unbailsed random coin and assign value to B[i] 
       and write B[i] into the current register. Let B[1] = 1 , B[0] = 0

3 P[i] exchanges its current register with P[1-i] and returns to step 1.

 hence P[1] = 0 and P[0] = 1

------------ Iteration - 2

Input: Registers C[0] and C[1] initialized to 0. Output: Exactly one of the register has the value #. 0 P[i] is initially scanning the register C[i] and

  has its local variable B[i] B =[1,0]

1 Read the current register and obtain a bit R[i]. Hence R[i] is now 0 2 Select one of three cases:

   (a) case [R[i] = #]: halt; -- False
   (b) case [R[i] = 0, B[i] = 1]: write # into the current register and halt; -- False
   (c) case [otherwise]: flip a unbailsed random coin and assign value to B[i] 
       and write B[i] into the current register. Let B[1] = 1 , B[0] = 0

3 P[i] exchanges its current register with P[1-i] and returns to step 1.

 hence P[1] = 1 and P[0] = 1

Name : Kunal Deshmukh Iteration - 1 Input: Registers C[0] and C[1] initialized to 0. Output: Exactly one of the register has the value #. 0 P[i] is initially scanning the register C[i] and has its local variable B[i] initialized to 0. 1 Read the current register and obtain a bit R[i]. Hence R[i] is now 0 2 Select one of three cases: (a) case [R[i] = #]: halt; -- False (b) case [R[i] = 0, B[i] = 1]: write # into the current register and halt; -- False (c) case [otherwise]: flip a unbailsed random coin and assign value to B[i] and write B[i] into the current register. Let B[1] = 1 , B[0] = 0 3 P[i] exchanges its current register with P[1-i] and returns to step 1. hence P[1] = 0 and P[0] = 1 ---------------- Iteration - 2 Input: Registers C[0] and C[1] initialized to 0. Output: Exactly one of the register has the value #. 0 P[i] is initially scanning the register C[i] and has its local variable B[i] B =[1,0] 1 Read the current register and obtain a bit R[i]. Hence R[i] is now 0 2 Select one of three cases: (a) case [R[i] = #]: halt; -- False (b) case [R[i] = 0, B[i] = 1]: write # into the current register and halt; -- False (c) case [otherwise]: flip a unbailsed random coin and assign value to B[i] and write B[i] into the current register. Let B[1] = 1 , B[0] = 0 3 P[i] exchanges its current register with P[1-i] and returns to step 1. hence P[1] = 1 and P[0] = 1

-- Feb 28 In-Class Exercise Thread

Initially C[0] = 0 and C[1] = 0 P[0] is scanning C[0] B[0]=0 Read C[0] and obtain R[0] case[R[0]!=# R[0]=0 B[0] = rand(0,1) C[0] = B[0] P[0] exchanges its current register with P[1], thus, P[0] now has C[1] and P[1] has C[0] The algorithm goes back to Step 1 This time B[0] = 1 So C[0] = 1 as per case 3 If rand(0,1) would make C[0] = 0 and C[1] = 0, the situation would repeat. P[0] reads C[1] and P[1] reads C[0] Here C[0] =1 and C[1] = 0 P[1] reads C[0] Thus R[0]!=# So case 2 R[0]=0 and B[1]= 1 So C[1] = # Thus the algorithm halts in the next step as it finds a #

(Edited: 2018-02-28)

<nowiki> Initially C[0] = 0 and C[1] = 0 P[0] is scanning C[0] B[0]=0 Read C[0] and obtain R[0] case[R[0]!=# R[0]=0 B[0] = rand(0,1) C[0] = B[0] P[0] exchanges its current register with P[1], thus, P[0] now has C[1] and P[1] has C[0] The algorithm goes back to Step 1 This time B[0] = 1 So C[0] = 1 as per case 3 If rand(0,1) would make C[0] = 0 and C[1] = 0, the situation would repeat. P[0] reads C[1] and P[1] reads C[0] Here C[0] =1 and C[1] = 0 P[1] reads C[0] Thus R[0]!=# So case 2 R[0]=0 and B[1]= 1 So C[1] = # Thus the algorithm halts in the next step as it finds a # </nowiki>

-- Feb 28 In-Class Exercise Thread

inputs : C[0] = C[1] = 0

Round 1:

0 - P[0] reads C[0], B[0] = 0

    P[1] reads C[1], B[1] = 0

1 - P[0] -> R[0] = 0

    P[1] -> R[1] = 0

2 - case c : B[0] = 1, B[1] = 0

    write B[0] current register  C[0] = 1, C[1] = 0

3 - exchange P[0] to look at C[1] and P[1] to look at C[0];

Round 2: 1 - R[0] = 0,B[0] = 1; R[1] = 1, B[1] = 1 2 - Case 2 since P[0] looks at assign, C[1] = # and halt P[0] 3 - P[0] looks at C[0]=0; P[1] looks at C[1]=# in Round 3 algorithm follows with C[1,#] and halts as per case 2(a)

(Edited: 2018-02-28)

inputs : C[0] = C[1] = 0 Round 1: 0 - P[0] reads C[0], B[0] = 0 P[1] reads C[1], B[1] = 0 1 - P[0] -> R[0] = 0 P[1] -> R[1] = 0 2 - case c : B[0] = 1, B[1] = 0 write B[0] current register C[0] = 1, C[1] = 0 3 - exchange P[0] to look at C[1] and P[1] to look at C[0]; Round 2: 1 - R[0] = 0,B[0] = 1; R[1] = 1, B[1] = 1 2 - Case 2 since P[0] looks at assign, C[1] = # and halt P[0] 3 - P[0] looks at C[0]=0; P[1] looks at C[1]=# in Round 3 algorithm follows with C[1,#] and halts as per case 2(a)

-- Feb 28 In-Class Exercise Thread

 c0 = 0, c1 = 0
 -------------------------------------------------
 b0=0, b1=0
 case 3 r0=0 b0=0, b0=0 r0=0
 case 3 r1=0 b1=0, b1=1 r1=1
 exchange current registers - r0=1 r1=0
 -------------------------------------------------
 case 3 b0=0 r0=1, b0=1 r0=1
 case 2 b1=1 r1=0, r1=# halt 
 Final C=[1,#]

(Edited: 2018-02-28)

c0 = 0, c1 = 0 ------------------------------------------------- b0=0, b1=0 case 3 r0=0 b0=0, b0=0 r0=0 case 3 r1=0 b1=0, b1=1 r1=1 exchange current registers - r0=1 r1=0 ------------------------------------------------- case 3 b0=0 r0=1, b0=1 r0=1 case 2 b1=1 r1=0, r1=# halt Final C=[1,#]