Yioop - PHP Search Engine

Feb 21 In-Class Exercise Thread.

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

Best,

Chris

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

-- Feb 21 In-Class Exercise Thread

 {3, -1, 5, 6, 2}
 p1 = 3, p2 = -1, p3 = 5, p4 = 6, p5 = 2
 Splitter -> 3 (p1)
 B's - {0,1,0,0,1}
 Rank of selecting the splitter S - {0, 1, 1, 1, 2} 
 p1 = 2 p2 = -1 p3 = 3	 p4 = 6 p5 = 5

 {2, -1}
 p1 = 2 p2 = -1
 Splitter -> 2 (p1)
 B's - {0,1}
 Rank of selecting the splitter - s = {0, 1}

 p1 = -1 p2 = 2

 {6, 5}
 p4 = 6 p5 = 5
 Splitter -> 6 (p5)
 B's - {0,1}
 Rank of selecting the splitter - s= {0, 1}

p4 = 5 p5 = 6

Finally-> p1 = -1 p2 = 2 p3 = 3 p4 = 5 p5 = 6

(Edited: 2018-02-21)

{3, -1, 5, 6, 2} p1 = 3, p2 = -1, p3 = 5, p4 = 6, p5 = 2 Splitter -> 3 (p1) B's - {0,1,0,0,1} Rank of selecting the splitter S - {0, 1, 1, 1, 2} p1 = 2 p2 = -1 '''p3 = 3''' p4 = 6 p5 = 5 {2, -1} p1 = 2 p2 = -1 Splitter -> 2 (p1) B's - {0,1} Rank of selecting the splitter - s = {0, 1} p1 = -1 p2 = 2 {6, 5} p4 = 6 p5 = 5 Splitter -> 6 (p5) B's - {0,1} Rank of selecting the splitter - s= {0, 1} p4 = 5 p5 = 6 Finally-> p1 = -1 p2 = 2 p3 = 3 p4 = 5 p5 = 6

-- Feb 21 In-Class Exercise Thread

{3, -1, 5, 6, 2} Pick a splitter at random. Let's say it was the 3rd element (5) Determine the rank of the splitter:

  Each processer sets bit in B if their element is less than the splitter
  B = [1,1,1,0,1]
  S = [1,2,3,3,4]
  Check: n/4 <= 4 <= 3n/4 fails

Redo: Pick a splitter at random. Let's say it was the 1st element (3) Determine the rank of the splitter:

  Each processer sets bit in B if their element is less than the splitter
  B = [1,1,0,0,1]
  S = [1,2,2,2,3]
  Check: n/4 <= 3 <= 3n/4 passes
  We then map any element where B[i] == 1 to C[s[i]]
  C = [3,-1,2,5,6]

We then recursively evaluate the array from indexes 0-2 and 4

{3, -1, 5, 6, 2} Pick a splitter at random. Let's say it was the 3rd element (5) Determine the rank of the splitter: Each processer sets bit in B if their element is less than the splitter B = [1,1,1,0,1] S = [1,2,3,3,4] Check: n/4 <= 4 <= 3n/4 fails Redo: Pick a splitter at random. Let's say it was the 1st element (3) Determine the rank of the splitter: Each processer sets bit in B if their element is less than the splitter B = [1,1,0,0,1] S = [1,2,2,2,3] Check: n/4 <= 3 <= 3n/4 passes We then map any element where B[i] == 1 to C[s[i]] C = [3,-1,2,5,6] We then recursively evaluate the array from indexes 0-2 and 4

-- Feb 21 In-Class Exercise Thread

 1. Randomly selecting one of the processors as splitter: Processor at last index of array       (value= 2)
 2. Value of B: {0,1,0,0,1}, S = 2
 3. Condition: (5)/(4) < S < (3)*(5)/(4) is True
 4. C = { -1, 2, 3, 5, 6} : Sorted

This splitter gives a sorted array in 1 iteration.

(Edited: 2018-02-21)

1. Randomly selecting one of the processors as splitter: Processor at last index of array (value= 2) 2. Value of B: {0,1,0,0,1}, S = 2 3. Condition: (5)/(4) < S < (3)*(5)/(4) is True 4. C = { -1, 2, 3, 5, 6} : Sorted This splitter gives a sorted array in 1 iteration.

-- Feb 21 In-Class Exercise Thread

processor 1 selects splitter A[2] = 5

each processor 1 to 5 , returns 1 if their element is <= splitter, otherwise 0: B = [1,1,1,0,1] Sn = 4 (Since, 4 > 3n/4 , therefore this step fails)

processor 1 selects splitter: A[0] = 3

each processor 1 to 5 , returns 1 if their element is <= splitter, otherwise 0: B = [1,1,0,0,1] Sn = 3 (Since, 3 < 3n/4 , this steps should pass) C = [3,-1,2,5,6]

quicksort(lowindex,Sn); quicksort(Sn + 1 ,lastindex);

Step 2: [3,-1,2] , [5,6]

(Edited: 2018-02-21)

processor 1 selects splitter A[2] = 5 each processor 1 to 5 , returns 1 if their element is <= splitter, otherwise 0: B = [1,1,1,0,1] Sn = 4 (Since, 4 > 3n/4 , therefore this step fails) processor 1 selects splitter: A[0] = 3 each processor 1 to 5 , returns 1 if their element is <= splitter, otherwise 0: B = [1,1,0,0,1] Sn = 3 (Since, 3 < 3n/4 , this steps should pass) C = [3,-1,2,5,6] quicksort(lowindex,Sn); quicksort(Sn + 1 ,lastindex); Step 2: [3,-1,2] , [5,6]

-- Feb 21 In-Class Exercise Thread

Selecting splitter as 2 Rank of splitter = 2

P1	P2	P3
-1	2	3,5,6

Selecting splitter as 5 Rank of splitter = 2

P1	P2	P3	P4	P5
-1	2	3	5	6

List is sorted

Selecting splitter as 2 Rank of splitter = 2 {| |- | P1 || P2 || P3 |- | -1 || 2 || 3,5,6 |} Selecting splitter as 5 Rank of splitter = 2 {| |- | P1 || P2 || P3 || P4 || P5 |- | -1 || 2 || 3 || 5 || 6 |} List is sorted

-- Feb 21 In-Class Exercise Thread

 items : {3, -1, 5, 6, 2}
 n = 5
 random no : 3

 p1: 3 = [(n)/(4),(3*n)/(4)]
 [(3)/(4),(9)/(4)] = since

 need to restart again

 randome no picked  = -1

 p1 = 3 , p2 = -1 , p3 = 5 , p4 = 6 , p5 = 2
 B = {1, 1, 0, 0, 1}

items : {3, -1, 5, 6, 2} n = 5 random no : 3 p1: 3 = [(n)/(4),(3*n)/(4)] [(3)/(4),(9)/(4)] = since need to restart again randome no picked = -1 p1 = 3 , p2 = -1 , p3 = 5 , p4 = 6 , p5 = 2 B = {1, 1, 0, 0, 1}

-- Feb 21 In-Class Exercise Thread

Pick the random splitter as 1st element -> (3)

B = [1,1,0,0,1] , S = [1,2,2,2,3]

Checking range : n/4 <= 3 <= 3n/4 (pass!)

Map elements where B[i] = 1 to C[S[i]]

Now C = [3,-1,2,5,6]

Recursively evaluate array for indexes [0-2] and [4]

(Edited: 2018-02-21)

Pick the random splitter as 1st element -> (3) B = [1,1,0,0,1] , S = [1,2,2,2,3] Checking range : n/4 <= 3 <= 3n/4 (pass!) Map elements where B[i] = 1 to C[S[i]] Now C = [3,-1,2,5,6] Recursively evaluate array for indexes [0-2] and [4]

-- Feb 21 In-Class Exercise Thread

 A = [3,-1,5,6,2]
 Splitter = 5 ; randomly choosen
 B = [1,1,1,0,1] ; 0 if value is greater than splitter, one otherwise
 S = [1,2,3,3,4]
 Rank of splitter = 4
 Not in range [5/4, 3*5/4] ; So repeat

 Splitter = 2
 B = [0,1,0,0,1]
 S = [0,1,1,1,2]
 Rank of splitter = 2
 In Range [5/4, 3*5/4]
 C = [-1,2,3,5,6]; For all B[i] = 1; place value A[i] in C[S[i]]
 Sorted

A = [3,-1,5,6,2] Splitter = 5 ; randomly choosen B = [1,1,1,0,1] ; 0 if value is greater than splitter, one otherwise S = [1,2,3,3,4] Rank of splitter = 4 Not in range [5/4, 3*5/4] ; So repeat Splitter = 2 B = [0,1,0,0,1] S = [0,1,1,1,2] Rank of splitter = 2 In Range [5/4, 3*5/4] C = [-1,2,3,5,6]; For all B[i] = 1; place value A[i] in C[S[i]] Sorted

-- Feb 21 In-Class Exercise Thread

Given:

An array P = [3, -1, 5, 6, 2], n = 5

5 processors

Show:

Computation steps involved for each processor for each step in QuickSort algorithm given in class.

Analysis:

---

Suppose we randomly chose 2nd element as the splitter, which is -1.

B = [0, 1, 0, 0, 0]

S = [0, 1, 1, 1, 1]

Check: n/4 <= S[4] <= 3n/4

1.25 <= S[4] <= 3.75 -> this step fails.

---

Let's try again, 1st element is now randomly chose as next splitter, which is 3.

B = [1, 1, 0, 0, 1]

S = [1, 2, 2, 2, 3]

Check: 1.25 <= S[4] <= 3.75 -> this step passes.

Put splitter 3 to P[2]. Any elements smaller than splitter is put in P[0-1] and elements larger than splitter is put in P[3-4].

P = [-1, 2, 3, 5, 6]

---

Then recursively do this with P[0-1] and P[3-4] until P is sorted.

(Edited: 2018-02-21)

---- Given: An array P = [3, -1, 5, 6, 2], n = 5 5 processors ---- Show: Computation steps involved for each processor for each step in QuickSort algorithm given in class. ---- Analysis: --- Suppose we randomly chose 2nd element as the splitter, which is -1. B = [0, 1, 0, 0, 0] S = [0, 1, 1, 1, 1] Check: n/4 <= S[4] <= 3n/4 1.25 <= S[4] <= 3.75 -> this step fails. --- Let's try again, 1st element is now randomly chose as next splitter, which is 3. B = [1, 1, 0, 0, 1] S = [1, 2, 2, 2, 3] Check: 1.25 <= S[4] <= 3.75 -> this step passes. Put splitter 3 to P[2]. Any elements smaller than splitter is put in P[0-1] and elements larger than splitter is put in P[3-4]. P = [-1, 2, 3, 5, 6] --- Then recursively do this with P[0-1] and P[3-4] until P is sorted.