The lecture say:

Definition: Let A be an algorithm. s: A is potential functionif: 1.s strictly decreases with every step of the algorithm 2.s has a lower bound We used this in the flipping game. We showed that: 1.The number of Ohio symbols would drop by at least one at each step. 2.Couldnt go below zero.

E (a) Determine if the following algorithm terminates. If so, prove this using the potential method as shown in lecture. If not, describe an input that would cause this algorithm not to terminate Input: A connected graph CG 1: function ALGORITHM(G) 2: Assign every vertex in G the color black 3: Let S be an empty stack 4 Choose an arbitrary vertex v e G and assign it the color red 5 PUSH(S,v) // Push v onto the stack 6: hile S is not empty do 7: 8: 9: uPoP(S) // Pop a node off the stack and assign it to u for each neighbor t of u do if t is colored black then 10: if u is colored red then Assign t the color blue else 12: 13: 14: 15: 16: 17 eturn Note: If you need a refresher on what stacks are, click here Assign t the color red PUSH(S, t) return False else if t and u have the same color then (b) Optional bonus. The above algorithm determines (or attempts to determine, depending on what you concluded in (a)) if its input graph G has a particular property. What is this property