(110 pts.) An Iterative Graph Algorithm Suppose you are controlling a robot moving around on a directed graph G =(V,E), where the vertices are locations and edges indicate ways the robot can move between them. The robot starts out at a vertex s EV, and you need to drive it to a goal vertex g V. However, some of the locations W CV are wet, and when the robot enters such a location it can slip and end up following any of the outgoing edges, not necessarily the one you want. You want to know whether there is some strategy you can follow to ensure the robot will reach g. To solve this problem, observe that if we are at a vertex v which has an edge to g, then if v is not wet, we're done: we can just follow that edge and reach g. However, if v is wet (VE W), then if there is an edge to some other vertex u, we can't guarantee we'll take the one leading to g. On the other hand, there can still be hope, if we can get to g from u: In this example, even if u is wet, although we can't control which of the two edges we take from v, we will still reach g: if we end up at u, we are forced to go to g next since there is only 1 outgoing edge. Let's say that a vertex v is good if we can always reach g from it, regardless of what happens at wet vertices; then in the example above, v, u, and g are good, but w is not. Generalizing the example, we have that a vertex v is good if and only if: v = 8, or v is dry and some outgoing edge leads to a good vertex, or vis wet and every outgoing edge leads to good vertex. This observation leads to the following iterative algorithm for our problem: 4: 1: function ALWAYS-REACHABLE(G=(V,E), SEV, SEV.W CV) 2: R+ {g} # set of known good vertices 3: while true do #iterate until R stops growing Nempty list # vertices to add to R for u EVR do if & W then if there is some edge (u, v) E E with v ER then add u to N else # u is wet; can't control what outgoing edge we take if all edges (u, v) E satisfy ve R then | add u to N if N is empty then break # no new vertices to add; terminate main loop else Add all vertices in N to R return whether s ER 16: et's prove that this algorithm is correct in a few stages. (a) (20 pts.) Prove that the algorithm always terminates. (b) (40 pts.) Let I be the statement "if we have done k iterations of the main loop so far, R is the set of good vertices from which we can always reach g in