Problem 2: Evacuating a building. In an emergency, a building has to be evacuated in a hurry. When a disaster strikes, an evacuation plan should be in place and there are many aspects that such a plan takes into consideration: https://www.osha.gov/SLTC/etools/evacuation/evac.html. Let us consider a much simplified version. Let G-(V, E) be a directed graph, representing a building. Every vertex vEV represents a room, and every edge (u,v) E E represents a corridor that leads from room u to room v (there may be also an edge (v, u)). For every corridor (u,v) E E, at most cu,u people can traverse it simultaneously in the direction from u to v, where Cu,u s a positive integer. Traversing a corridor takes one time step, and traversing a room takes zero time. Suppose that there are k people in the building, all initially located in some room s V, and they all want to move to some room t V (e.g., exit). Give an algorithm that computes the fastest possible way for all people to move from room s to room t. The running time of your algorithm should be polynomial in both n, and k (for example, O(IV10k10)) Hint: Clearly, this problem seems related to the max-flow problem. However, an additional complication in building evacuation is that the algorithm has to account for time. One possible approach for overcoming this obstacle is as follows: First, argue that the maximum time necessary to evacuate the building it at most O(kn) (why?). It is enough to solve the following simpler "decision" version of the problem: Given some integer T, find a way to evacuate the building in at most T steps, if possible. Given an algorithm for the decision problem we can solve the original problem by trying all O(kn) possible values for T. Finally, show that the decision problem can be reduced to a max-flow computation; that is, construct a flow network Nr, such that the building can be evacuated in at most T steps, if and only if the max-flow in Nr has value at least k. https://sigcse2018.sigcse.org/reviewers/review-bidding.html Problem 2: Evacuating a building. In an emergency, a building has to be evacuated in a hurry. When a disaster strikes, an evacuation plan should be in place and there are many aspects that such a plan takes into consideration: https://www.osha.gov/SLTC/etools/evacuation/evac.html. Let us consider a much simplified version. Let G-(V, E) be a directed graph, representing a building. Every vertex vEV represents a room, and every edge (u,v) E E represents a corridor that leads from room u to room v (there may be also an edge (v, u)). For every corridor (u,v) E E, at most cu,u people can traverse it simultaneously in the direction from u to v, where Cu,u s a positive integer. Traversing a corridor takes one time step, and traversing a room takes zero time. Suppose that there are k people in the building, all initially located in some room s V, and they all want to move to some room t V (e.g., exit). Give an algorithm that computes the fastest possible way for all people to move from room s to room t. The running time of your algorithm should be polynomial in both n, and k (for example, O(IV10k10)) Hint: Clearly, this problem seems related to the max-flow problem. However, an additional complication in building evacuation is that the algorithm has to account for time. One possible approach for overcoming this obstacle is as follows: First, argue that the maximum time necessary to evacuate the building it at most O(kn) (why?). It is enough to solve the following simpler "decision" version of the problem: Given some integer T, find a way to evacuate the building in at most T steps, if possible. Given an algorithm for the decision problem we can solve the original problem by trying all O(kn) possible values for T. Finally, show that the decision problem can be reduced to a max-flow computation; that is, construct a flow network Nr, such that the building can be evacuated in at most T steps, if and only if the max-flow in Nr has value at least k. https://sigcse2018.sigcse.org/reviewers/review-bidding.html