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

Best,

Chris

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

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

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

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)

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

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

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

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

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.