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

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

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

-- 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)

-- 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.

-- May 2 In-Class Exercise Thread

<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

<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

<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.