3. Pesky Particles. You are assisting with the following physics experiment: after a chemical process occurs two sub-atomic particles (say Pi and p2) will appear on a graph-structure G = (V, E) at nodes s and t. The goal of the experiment is to safely move pi and p2 to the terminal nodes of the graph s' and t'. Each step of the experiment moves both particles along some edge of the graph. That is: the first step moves p1 across an edge connected to s and simultaneously moves P2 across an edge connected to t. the second step again simultaneously moves both p and p2 along some edges. etc. The worry is if either particle gets to close to the other, then it is possible them to break away from the graph and collide with one another, ruining the experiment to say the least. The designers of the graph tell you that as long as the number of edges between the two particles is strictly greater than then there is no chance of the particles colliding. That is if d(u, v) denotes the number of edges in a shortest u-v path, then we must maintain that minu, d(u, v) > for all positions of pi and P2 as they move along their respective paths. We may assume that the starting and ending positions are safe, i.e., d(s, t) > and dis', t')> . [7] (a) Design and analyse an efficient algorithm that determines whether it is possible or not to route the particles safely in the given graph. What is the runtime of your algorithm as a function of n, the number of vertices in the graph? [5] (b) Now suppose rather than having only two particles, we had n/1000 particles. Consider generalizing your algorithm to handle these n/1000 particles. Provide a Big-O bound (as accurate as you can) for the running time of your algorithm. 3. Pesky Particles. You are assisting with the following physics experiment: after a chemical process occurs two sub-atomic particles (say Pi and p2) will appear on a graph-structure G = (V, E) at nodes s and t. The goal of the experiment is to safely move pi and p2 to the terminal nodes of the graph s' and t'. Each step of the experiment moves both particles along some edge of the graph. That is: the first step moves p1 across an edge connected to s and simultaneously moves P2 across an edge connected to t. the second step again simultaneously moves both p and p2 along some edges. etc. The worry is if either particle gets to close to the other, then it is possible them to break away from the graph and collide with one another, ruining the experiment to say the least. The designers of the graph tell you that as long as the number of edges between the two particles is strictly greater than then there is no chance of the particles colliding. That is if d(u, v) denotes the number of edges in a shortest u-v path, then we must maintain that minu, d(u, v) > for all positions of pi and P2 as they move along their respective paths. We may assume that the starting and ending positions are safe, i.e., d(s, t) > and dis', t')> . [7] (a) Design and analyse an efficient algorithm that determines whether it is possible or not to route the particles safely in the given graph. What is the runtime of your algorithm as a function of n, the number of vertices in the graph? [5] (b) Now suppose rather than having only two particles, we had n/1000 particles. Consider generalizing your algorithm to handle these n/1000 particles. Provide a Big-O bound (as accurate as you can) for the running time of your algorithm
