Please post your solutions to the May 4 In-Class Exercise to this thread. Best, Chris

-- May 4 In-Class Exercise Thread

((resource:Screen Shot 2022-05-04 at 5.47.08 PM.jpg|Resource Description for Screen Shot 2022-05-04 at 5.47.08 PM.jpg))

-- May 4 In-Class Exercise Thread

G = (V, E), V = {1, 2, 3, 4}, E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}, w = {1, 2, 3, 1, 2, 1} The triangle inequality states that the sum of any two sides of a triangle is greater than or equal to the third side. We can verify that the graph obeys the triangle inequality as follows: (1, 2), (1, 3), (2, 3): 1 + 2 >= 1, 1 + 1 >= 2, 2 + 1 >= 1 (1, 2), (1, 4), (2, 4): 1 + 3 >= 2, 1 + 2 >= 3, 3 + 2 >= 1 (1, 3), (1, 4), (3, 4): 2 + 3 >= 1, 2 + 1 >= 3, 3 + 1 >= 2 (2, 3), (2, 4), (3, 4): 1 + 2 >= 1, 1 + 1 >= 2, 2 + 1 >= 1 Thus, the graph obeys the triangle inequality. ---- APPROX-TSP-TOUR (abbreviated as ATT) would compute a tour on this graph as follows: '''ATT1:''' Select vertex to be root (arbitrarily choose r = 1) '''ATT2:''' Compute MST-PRIM(G, w, r) (abbreviated as MT) '''MT1-MT3:''' key = {infty, infty, infty, infty}, pi = {NIL, NIL, NIL, NIL} '''MT4-MT5:''' key = {0, infty, infty, infty}, pi = {0, NIL, NIL, NIL} '''MT6:''' Q = MAKE-QUEUE(G.V) = {1, 2, 3, 4} ''Loop 1'' '''MT7-MT9:''' Q != 0, u = EXTRACT-MIN(Q) = 1, G.adj[u] = {2, 3, 4} <u>v = 2</u> '''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 0 + 1 < infty -> true '''MT11-MT12:''' v.pi = 1, v.key = u.key + w(u, v) = 0 + 1 = 1 <u>v = 3</u> '''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 0 + 2 < infty -> true '''MT11-MT12:''' v.pi = 1, v.key = u.key + w(u, v) = 0 + 2 = 2 <u>v = 4</u> '''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 0 + 3 < infty -> true '''MT11-MT12:''' v.pi = 1, v.key = u.key + w(u, v) = 0 + 3 = 3 ''Loop 2'' '''MT7-MT9:''' Q != 0, u = EXTRACT-MIN(Q) = 2, G.adj[u] = {1, 3, 4} <u>v = 1</u> '''MT10:''' v not in Q -> false <u>v = 3</u> '''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 1 + 1 < 2 -> false <u>v = 4</u> '''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 1 + 2 < 3 -> false ''Loop 3'' '''MT7-MT9:''' Q != 0, u = EXTRACT-MIN(Q) = 3, G.adj[u] = {1, 2, 4} <u>v = 1</u> '''MT10:''' v not in Q -> false <u>v = 2</u> '''MT10:''' v not in Q -> false <u>v = 4</u> '''MT10:''' v in Q -> true, u.key + w(u, v) < v.key -> 2 + 1 < 3 -> false ''Loop 4'' '''MT7-MT9:''' Q != 0, u = EXTRACT-MIN(Q) = 4, G.adj[u] = {1, 2, 3} <u>v = 1</u> '''MT10:''' v not in Q -> false <u>v = 2</u> '''MT10:''' v not in Q -> false <u>v = 3</u> '''MT10:''' v not in Q -> false '''ATT2:''' return MST = {1, 2, 3, 4} '''ATT3:''' L = {1, 2, 3, 4} '''ATT4:''' H = {1, 2, 3, 4}

-- May 4 In-Class Exercise Thread

((resource:WhatsApp Image 2022-05-06 at 12.56.59 PM.jpeg|Resource Description for WhatsApp Image 2022-05-06 at 12.56.59 PM.jpeg)) ((resource:WhatsApp Image 2022-05-06 at 12.56.59 PM (1).jpeg|Resource Description for WhatsApp Image 2022-05-06 at 12.56.59 PM (1).jpeg))

-- May 4 In-Class Exercise Thread

((resource:627841d6838a762d30d8c9c0.png|Resource Description for 627841d6838a762d30d8c9c0.png))

-- May 4 In-Class Exercise Thread

((resource:may4.jpeg|Resource Description for may4.jpeg))

-- May 4 In-Class Exercise Thread

<nowiki> There are 4 possible triangles in this graph, enumerated below. Triangle 1,2,4 d(1,2) + d(2,4) >= d(1,4) 1 + 2 >= 3, inequality holds d(1,4) + d(4,2) >= d(1,2) 3 + 2 >= 1, inequality holds d(1,1) + d(4,2) >= d(4,2) 1+ 2 >= 2, inequality holds Triangle 1,2,3 d(1,2) + d(2,3) >= d(1,3) 1 + 1 >= 2, inequality holds d(2,3) + d(1, 3) >= d(1,2) 1 + 2 >= 1, inequality holds d(1,2) + d(1,3) >= d(3,2) 1+ 2 >= 1, inequality holds Triangle 1,3,4 d(1,3) + d(1,4) >= d(4,3) 2 + 3 >= 1, inequality holds d(1,3) + d(3, 4) >= d(1,4) 2 + 1 >= 3, inequality holds d(1,4) + d(3,4) >= d(1,3) 3+ 1 >= 2, inequality holds Triangle 2,3,4 d(2,3) + d(3,4) >= d(2,4) 1 + 1 >= 2, inequality holds d(2,4) + d(3, 4) >= d(2,3) 2 + 1 >= 1, inequality holds d(2,3) + d(2,4) >= d(3,4) 1+ 2 >= 1, inequality holds Thus, all the edges in the graph obey the triangle inequality. APPROX-TSP-TOUR: Pick vertex 1 to be the root. Q - 1, 0, 0 2, inf, NILL 3, inf, NILL 4, inf, NILL Q!=0 Loop 1 U = 1,0,0 V = 2 , 0+1 < inf, true V = 3 , 0+2 < inf, true V = 4 , 0+3 < inf, true Q - 2, 1, 1 3, 2, 1 4, 3, 1 Q!=0 Loop 2 U = 2,1,1 V = 3 , 1+1 < 2, true V = 4 , 1+2 < 3, false Q - 3, 2, 1 4, 3, 1 Q!=0 Loop 3 U = 3,1,1 V = 4 , 1+2 < 3, false Q - 4, 3, 1 Q!=0 Loop 4 U = 4,3,1 V = empty set MST-PRIM returns {1,2,3,4} Traversal would be 1,2,3,4 if we’re ordering by the size. Cost of tree traversal for this route is 1 + 1 + 1 + 3 = 6 (the last 3 is to go back to the root) </nowiki>

-- May 4 In-Class Exercise Thread

ATT 1 root 1
ATT 2 -----> MST(G,w,1)
            u.key= {inf, inf, inf, inf} ; u.pi = {NIL, NIL, NIL, NIL}
            r.key = 0 r.pi = 0 
            Q = {1,2,3,4}
            while Q!=0
            u = ExtractMin(Q) = 1 Q = {2,3,4}
            for each v in G.adj[u] {2,3,4}
            {2} 2 is in Q and inf+1 < inf
              2.pi = 1  {0, 1, inf, inf}
              2.key = 0 + 1 = 1 {0, 1, NIL, NIL}
            {3} 3 is in Q and 0+2 < inf
                3.pi = 1  {0, 1, 1, inf}
                3.key = 0 + 2 = 2 {0, 1, 2, NIL}
            {4} 4 is in Q and 0+3 < inf
                4.pi = 1  {0, 1, 1, inf}
                4.key = 0 + 3 = 3 {0, 1, 2, 3}
                
            u = ExtractMin(Q) = 2 Q = {3,4}
            for each v in G.adj[u] {1,4,3}
                {1} 1 is not in Q so no if execution
                {4} 4 is in Q and 1+2 !< 3 so no if execution
                {3} 3 is in Q and 1+1 !< 2 so no if execution 
 
            u = ExtractMin(Q) = 3 Q = {4}
            for each v in G.adj[u] {1,2,4}
                {1} 1 is not in Q so no if execution
                {2} 2 is in Q  so no if execution
                {4} 4 is in Q and 2+1 !< 3 so no if execution       
 
            u = ExtractMin(Q) = 4 Q = {}
            for each v in G.adj[u] {1,2,3}
                {1} 1 is not in Q so no if execution
                {2} 2 is in Q  so no if execution
                {3} 3 is in Q so no if execution
returns {1,2,3,4}
L = {1,2,3,4}
H= {1,2,3,4} 
 
Cost = 1+1+1+3 = 6 units

((resource:WhatsApp Image 2022-05-08 at 10.00.53 PM.jpeg|Resource Description for WhatsApp Image 2022-05-08 at 10.00.53 PM.jpeg)) <pre> ATT 1 root 1 ATT 2 -----> MST(G,w,1) u.key= {inf, inf, inf, inf} ; u.pi = {NIL, NIL, NIL, NIL} r.key = 0 r.pi = 0 Q = {1,2,3,4} while Q!=0 u = ExtractMin(Q) = 1 Q = {2,3,4} for each v in G.adj[u] {2,3,4} {2} 2 is in Q and inf+1 < inf 2.pi = 1 {0, 1, inf, inf} 2.key = 0 + 1 = 1 {0, 1, NIL, NIL} {3} 3 is in Q and 0+2 < inf 3.pi = 1 {0, 1, 1, inf} 3.key = 0 + 2 = 2 {0, 1, 2, NIL} {4} 4 is in Q and 0+3 < inf 4.pi = 1 {0, 1, 1, inf} 4.key = 0 + 3 = 3 {0, 1, 2, 3} u = ExtractMin(Q) = 2 Q = {3,4} for each v in G.adj[u] {1,4,3} {1} 1 is not in Q so no if execution {4} 4 is in Q and 1+2 !< 3 so no if execution {3} 3 is in Q and 1+1 !< 2 so no if execution u = ExtractMin(Q) = 3 Q = {4} for each v in G.adj[u] {1,2,4} {1} 1 is not in Q so no if execution {2} 2 is in Q so no if execution {4} 4 is in Q and 2+1 !< 3 so no if execution u = ExtractMin(Q) = 4 Q = {} for each v in G.adj[u] {1,2,3} {1} 1 is not in Q so no if execution {2} 2 is in Q so no if execution {3} 3 is in Q so no if execution returns {1,2,3,4} L = {1,2,3,4} H= {1,2,3,4} Cost = 1+1+1+3 = 6 units </pre>

-- May 4 In-Class Exercise Thread

((resource:IMG-2549.jpg|Resource Description for IMG-2549.jpg))

-- May 4 In-Class Exercise Thread

((resource:5B47710C-5CE4-4454-A256-ED105C4F5094_1_105_c.jpeg|Resource Description for 5B47710C-5CE4-4454-A256-ED105C4F5094_1_105_c.jpeg)) ((resource:3A8FC20B-66D9-4F7D-B618-99C0AD2D3570_1_105_c.jpeg|Resource Description for 3A8FC20B-66D9-4F7D-B618-99C0AD2D3570_1_105_c.jpeg))