Post your solutions to the May 9 In-Class Exercise to this thread. Best, Chris

-- May 9 In-Class Exercise Thread

 let X = {}
 let Y = {}
 
 for A:
  X = {A}; Y = {}
 for B:
  X = {A,B}; Y = {}
 for C:
  X = {A,B}; Y = {C}
 for D:
  X = {A,B,D}; Y = {C}
 for E:
  X = {A,B,D}; Y = {C,E}
 for F:
  X = {A,B,D,F}; Y = {C,E}
 for G:
  X = {A,B,D,F}; Y = {C,E,G}
 for H:
  X = {A,B,D,F,H}; Y = {C,E,G}
 for I:
  X = {A,B,D,F,H,I}; Y = {C,E,G}
 for J:
  X = {A,B,D,F,H,I,J}; Y = {C,E,G}

 disjoint edges = {AE,EJ,ED,GB,GJ,GI} 
 X = {A,B,D,F,H,I,J}; Y = {C,E,G}
 Cut size = 9

((resource:IMG_20180509_135650.jpg|Resource Description for IMG_20180509_135650.jpg)) labelling is as above There's 15 edges and 10 vertices let E = {A,B,C,D,E,F,G,H,I,J} let X = {} let Y = {} for A: X = {A}; Y = {} for B: X = {A,B}; Y = {} for C: X = {A,B}; Y = {C} for D: X = {A,B,D}; Y = {C} for E: X = {A,B,D}; Y = {C,E} for F: X = {A,B,D,F}; Y = {C,E} for G: X = {A,B,D,F}; Y = {C,E,G} for H: X = {A,B,D,F,H}; Y = {C,E,G} for I: X = {A,B,D,F,H,I}; Y = {C,E,G} for J: X = {A,B,D,F,H,I,J}; Y = {C,E,G} disjoint edges = {AE,EJ,ED,GB,GJ,GI} X = {A,B,D,F,H,I,J}; Y = {C,E,G} Cut size = 9

-- May 9 In-Class Exercise Thread

Order of vertices: Number the outside points from 1-5 in clockwise order starting from the top Number the inside points from 6-10 in clockwise order starting from the top Need 15 flips: 0110100011 Graph A: (1,4,6,7,8) Graph B: (2,3,5,9,10)

-- May 9 In-Class Exercise Thread

((resource:unnamed.jpg|Resource Description for unnamed.jpg)) Cut size = 2

-- May 9 In-Class Exercise Thread

Coin flips = [1, 0, 1, 1, 0, 1, 0, 0, 1, 0] The vertices are arranged in an order in the clockwise direction Let the edges be A, B, C, D, E, F, G, H, I, J Assigning the vertices to either set a, or b a = [A, C, D, F, I] b = [B, E, G, H, J] The cut size is 6

-- May 9 In-Class Exercise Thread

((resource:Screenshot from 2018-05-09 14-03-15.png|Resource Description for Screenshot from 2018-05-09 14-03-15.png))

-- May 9 In-Class Exercise Thread

After 10 simultaneous online coin flips, we have: A = {1, 2, 5, 6, 7, 8, 9} B = {3, 4, 10} Hence, cut size is 7, which is within a factor of 2 of m = 15. Hence, MAX-CUT has returned the average case in this instance.

-- May 9 In-Class Exercise Thread

((resource:20180509_141108.jpg|Resource Description for 20180509_141108.jpg))

-- May 9 In-Class Exercise Thread

<nowiki>((resource:Screenshot from 2018-05-09 14-03-15.png|Resource Description for Screenshot from 2018-05-09 14-03-15.png)) </nowiki>

-- May 9 In-Class Exercise Thread

((resource:IMG_2709.JPG|Resource Description for IMG_2709.JPG))