(a) Determine if the following algorithm terminates. If so, prove this using the potential method If...

   

Transcribed Image Text:

(a) Determine if the following algorithm terminates. If so, prove this using the potential method If not, describe an input that would cause the algorithm to run forever. Require: A connected graph G 1: function ALGORITHM (G) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: Assign every vertex in G the color black Let S be an empty stack Choose an arbitrary vertex v E G and assign it the color red PUSH(S, V) while S is not empty do u ← POP(S) for each neighbor t of u do if t is colored black then if u is colored red then Assign t the color blue else Assign t the color red return True PUSH(S, t) else if t and u have the same color then return False ▷ Pop a node off the stack and assign it to u (b) Run the algorithm on the following graph and compute the value of the potential func- tion you generated for each iteration of the line 6 (the while loop). For line 4, choose A to be the arbitrary vertex. For line 8, start from the lexicographically smallest node if there is a choice of at least two nodes. B IN D A ▷ Push v onto the stack F E (a) Determine if the following algorithm terminates. If so, prove this using the potential method If not, describe an input that would cause the algorithm to run forever. Require: A connected graph G 1: function ALGORITHM (G) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: Assign every vertex in G the color black Let S be an empty stack Choose an arbitrary vertex v E G and assign it the color red PUSH(S, V) while S is not empty do u ← POP(S) for each neighbor t of u do if t is colored black then if u is colored red then Assign t the color blue else Assign t the color red return True PUSH(S, t) else if t and u have the same color then return False ▷ Pop a node off the stack and assign it to u (b) Run the algorithm on the following graph and compute the value of the potential func- tion you generated for each iteration of the line 6 (the while loop). For line 4, choose A to be the arbitrary vertex. For line 8, start from the lexicographically smallest node if there is a choice of at least two nodes. B IN D A ▷ Push v onto the stack F E