Yioop - PHP Search Engine

May 2 In-Class Exercise Thread.

Post your solutions to the May 2 In-Class Exercise to this Thread.

Best,

Chris

Post your solutions to the May 2 In-Class Exercise to this Thread. Best, Chris

-- May 2 In-Class Exercise Thread

  S1: {1,3,5},	C = {{1,3,5}}
  S2: {1,2}, 	C = {{1,3,5},{1,2}}
  S3: {4,5}, 	C = {{1,3,5},{1,2},{4,5}}
  S4: {5,6}, 	C = {{1,3,5},{1,2},{4,5},{5,6}}

  |S3 - (S1 U S2)| vs |{5,6} - (S1 U S2)|
  |{1}| = |{6}|
  1 = 1
  yes it obeys the inequality

(Edited: 2018-05-02)

S1: {1,3,5}, C = {{1,3,5}} S2: {1,2}, C = {{1,3,5},{1,2}} S3: {4,5}, C = {{1,3,5},{1,2},{4,5}} S4: {5,6}, C = {{1,3,5},{1,2},{4,5},{5,6}} |S3 - (S1 U S2)| vs |{5,6} - (S1 U S2)| |{1}| = |{6}| 1 = 1 yes it obeys the inequality

-- May 2 In-Class Exercise Thread

 X={1,2,3,4,5,6}
 F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}}
 ---------------------
 U=X
 C=0
 ---------------------
 S1={1,3,5}
 U={2,4,6}
 C={{1,3,5}}
 ---------------------
 S2={4,6}
 U={4,6}
 C={{1,3,5},{1,2}}
 ---------------------
 S3={4,5}
 U={6}
 C={{1,3,5},{1,2},{4,5}}
 ---------------------
 S4={5,6}
 U=0
 C={{1,3,5},{1,2},{4,5},{5,6}}
 ---------------------

 |S3-(S1 U S2)| = |{4}| = 1
 |{5,6} - (S1 U S2)| = |{6}| = 1

 Yes it obeys the inequality

(Edited: 2018-05-02)

X={1,2,3,4,5,6} F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} --------------------- U=X C=0 --------------------- S1={1,3,5} U={2,4,6} C={{1,3,5}} --------------------- S2={4,6} U={4,6} C={{1,3,5},{1,2}} --------------------- S3={4,5} U={6} C={{1,3,5},{1,2},{4,5}} --------------------- S4={5,6} U=0 C={{1,3,5},{1,2},{4,5},{5,6}} --------------------- |S3-(S1 U S2)| = |{4}| = 1 |{5,6} - (S1 U S2)| = |{6}| = 1 Yes it obeys the inequality

-- May 2 In-Class Exercise Thread

 X = {1,2,3,4,5,6} 
 and 
 F = {{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}}
 
 U = X
 C = {}

Round 1

  select s = {1,3,5} since it maximizes s ^^ U
  U = {2,4,6}
  C = {{1,3,5}}

Round 2

 select s = {1,2}
 U = {4,6}
 C = {{1,3,5},{1,2}}

Round 3

 select s = {4,5}
 U = {6}
 C = {{1,3,5},{1,2},{4,5}}

Round 4

 select s = {5,6}
 U = {}
 C = {{1,3,5},{1,2},{4,5}, {5,6}}

  |S3 - (S1 U S2)| = 1
  |{5,6} - (S1 U S2) | = 1

  1 is equal to 1, therefore, |Si−(S1∪S2∪...∪Si−1)|≥|S−(S1∪S2∪...∪Si−1)|is obeyed

(Edited: 2018-05-02)

X = {1,2,3,4,5,6} and F = {{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} U = X C = {} Round 1 select s = {1,3,5} since it maximizes s ^^ U U = {2,4,6} C = {{1,3,5}} Round 2 select s = {1,2} U = {4,6} C = {{1,3,5},{1,2}} Round 3 select s = {4,5} U = {6} C = {{1,3,5},{1,2},{4,5}} Round 4 select s = {5,6} U = {} C = {{1,3,5},{1,2},{4,5}, {5,6}} |S3 - (S1 U S2)| = 1 |{5,6} - (S1 U S2) | = 1 1 is equal to 1, therefore, |Si−(S1∪S2∪...∪Si−1)|≥|S−(S1∪S2∪...∪Si−1)|is obeyed

-- May 2 In-Class Exercise Thread

 X = {1,2,3,4,5,6}
 F = {{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}}
 
 U = X
 Iteration1
 S1 = {1,3,5}
 U = {2,4,6}
 C = {1,3,5}
 
 Iteration2
 S2 = {2,3}
 U = {4,6}
 C = {{1,3,5},{2,3}}

 Iteration3
 S3 = {4,5}
 U = {6}
 C = {{1,3,5},{2,3},{4,5}}
 
 Iteration4
 S4 = {5,6}
 U = {}
 C = {{1,3,5},{2,3},{4,5},{5,6}}

 |S3 - (S1US2)|  = 1
 (S1US2) = {1,2,3,5}
  S3 = {4,5}

 |{5,6} - (S1US2)| = 1

 So |S3 - (S1US2)| >= |{5,6} - (S1US2)| (1 = 1 ; inequality holds)

(Edited: 2018-05-02)

X = {1,2,3,4,5,6} F = {{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} U = X Iteration1 S1 = {1,3,5} U = {2,4,6} C = {1,3,5} Iteration2 S2 = {2,3} U = {4,6} C = {{1,3,5},{2,3}} Iteration3 S3 = {4,5} U = {6} C = {{1,3,5},{2,3},{4,5}} Iteration4 S4 = {5,6} U = {} C = {{1,3,5},{2,3},{4,5},{5,6}} |S3 - (S1US2)| = 1 (S1US2) = {1,2,3,5} S3 = {4,5} |{5,6} - (S1US2)| = 1 So |S3 - (S1US2)| >= |{5,6} - (S1US2)| (1 = 1 ; inequality holds)

-- May 2 In-Class Exercise Thread

Answer 1

First we will start with the set {1,3,5}. This leaves the set {2,4,6} The greedy algorithm will chose {1,2}, giving us a C = {{1,3,5},{1,2}} and a U = {4,6} The greedy algorithm will chose {4,5}, giving us a C = {{1,3,5},{1,2},{4,5}} and a U = {6} Finally, the greedy algorithm will chose {1,6}, giving us a C = {{1,3,5},{1,2},{4,5},{1,6}} and a U = $\emptyset$.

Answer 2

|{4,5} - {1,2} + {1,3,5}| = |{5,6} - {1,2} + {1,3,5}|

These are equal and therefore the equality holds.

'''Answer 1 ''' First we will start with the set {1,3,5}. This leaves the set {2,4,6} The greedy algorithm will chose {1,2}, giving us a C = {{1,3,5},{1,2}} and a U = {4,6} The greedy algorithm will chose {4,5}, giving us a C = {{1,3,5},{1,2},{4,5}} and a U = {6} Finally, the greedy algorithm will chose {1,6}, giving us a C = {{1,3,5},{1,2},{4,5},{1,6}} and a U = $\emptyset$. '''Answer 2''' |{4,5} - {1,2} + {1,3,5}| = |{5,6} - {1,2} + {1,3,5}| These are equal and therefore the equality holds.

-- May 2 In-Class Exercise Thread

Kunal Deshmukh X = {1,2,3,4,5,6} F = {{2,3},{4,5},{5,6},{1,6}} U = X C = null step 1: U = {2,4,6 } C = {1,3,5} step 2: U = {1,2,4,6} C = C u {S}

<nowiki> Kunal Deshmukh X = {1,2,3,4,5,6} F = {{2,3},{4,5},{5,6},{1,6}} U = X C = null step 1: U = {2,4,6 } C = {1,3,5} step 2: U = {1,2,4,6} C = C u {S} </nowiki>

-- May 2 In-Class Exercise Thread

X={1,2,3,4,5,6} and F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} Ans:1 U=X C= {} (1) S = { 1,3,5}, U = {2,4,6} C = { {1,3,5} } (2) S = { 1,2}, U = {4,6} C = { {1,3,5} , {1,2} } (3) S = { 4,5}, U = {6} C = { {1,3,5} , {1,2}, { 4,5} } (4) S = { 5,6}, U = {} C = { {1,3,5} , {1,2}, { 4,5}, {5,6} } ans = C = { {1,3,5} , {1,2}, { 4,5}, {5,6} } Ans :2 Compare: |S3−(S1∪S2)| versus |{5,6}−(S1∪S2)|. |{4}| versus |{6}| 1 versus 1 1

(Edited: 2018-05-02)

<nowiki> X={1,2,3,4,5,6} and F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} Ans:1 U=X C= {} (1) S = { 1,3,5}, U = {2,4,6} C = { {1,3,5} } (2) S = { 1,2}, U = {4,6} C = { {1,3,5} , {1,2} } (3) S = { 4,5}, U = {6} C = { {1,3,5} , {1,2}, { 4,5} } (4) S = { 5,6}, U = {} C = { {1,3,5} , {1,2}, { 4,5}, {5,6} } ans = C = { {1,3,5} , {1,2}, { 4,5}, {5,6} } Ans :2 Compare: |S3−(S1∪S2)| versus |{5,6}−(S1∪S2)|. |{4}| versus |{6}| 1 versus 1 1 <= 1, so yes it does obey the inequality of the previous slide </nowiki>

-- May 2 In-Class Exercise Thread

Given: X={1,2,3,4,5,6} and F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} U=X C= {} S1 = { 1,3,5}, U = {2,4,6} C = {{1,3,5}} S2 = { 1,2}, U = {4,6} C = {{1,3,5} , {1,2}} S3 = { 4,5}, U = {6} C = {{1,3,5} , {1,2}, { 4,5}} S4 = { 5,6}, U = {} C = {{1,3,5} , {1,2}, { 4,5}, {5,6}} |S3−(S1∪S2)| versus |{5,6}−(S1∪S2)| ==> |{4}| versus |{6}| 1 versus 1 Here, 1

<nowiki> Given: X={1,2,3,4,5,6} and F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} U=X C= {} S1 = { 1,3,5}, U = {2,4,6} C = {{1,3,5}} S2 = { 1,2}, U = {4,6} C = {{1,3,5} , {1,2}} S3 = { 4,5}, U = {6} C = {{1,3,5} , {1,2}, { 4,5}} S4 = { 5,6}, U = {} C = {{1,3,5} , {1,2}, { 4,5}, {5,6}} |S3−(S1∪S2)| versus |{5,6}−(S1∪S2)| ==> |{4}| versus |{6}| 1 versus 1 Here, 1 <= 1, Thus, it satisfies the inequality of the previous slide </nowiki>

-- May 2 In-Class Exercise Thread

Given X={1,2,3,4,5,6} and F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}}

Initially

 U=X
 C={0}
 
 S1={1,3,5}
 U={2,4,6}
 C={{1,3,5}}

 S2={4,6}
 U={4,6}
 C={{1,3,5},{1,2}}

 S3={4,5}
 U={6}
 C={{1,3,5},{1,2},{4,5}}

 S4={5,6}
 U=0
 C={{1,3,5},{1,2},{4,5},{5,6}}

 |S3-(S1 U S2)| = |{4}| = 1,  |{5,6} - (S1 U S2)| = |{6}| = 1

Inequality law is being obeyed.

(Edited: 2018-05-02)

Given X={1,2,3,4,5,6} and F={{1,2},{2,3},{4,5},{5,6},{1,6},{1,3,5}} Initially U=X C={0} S1={1,3,5} U={2,4,6} C={{1,3,5}} S2={4,6} U={4,6} C={{1,3,5},{1,2}} S3={4,5} U={6} C={{1,3,5},{1,2},{4,5}} S4={5,6} U=0 C={{1,3,5},{1,2},{4,5},{5,6}} |S3-(S1 U S2)| = |{4}| = 1, |{5,6} - (S1 U S2)| = |{6}| = 1 Inequality law is being obeyed.