For problems that require you to provide an algorithm, you must give the following:

1. a precise description of the algorithm in English and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

2. Let G = (V, E) be a directed graph with s,te V and positive edge capacities. We call an edge a flow-stopper if its deletion would shrink the maximum flow from s to t. (a) Prove or disprove the following statements: i. If e is a flow-stopper, then there is a minimum s-t cut that it crosses. ii. If we can find a minimum s-t cut that e crosses, then we know e is a flow-stopper. (b) Design an alogrithm that takes in a graph G (with all of the properites above), a max st flow f for G, and an edge e', and decides if e' is a flow-stopper. Your algorithm should have a runtime of O(|E| - cel), where cel is the capacity of e'. 2. Let G = (V, E) be a directed graph with s,te V and positive edge capacities. We call an edge a flow-stopper if its deletion would shrink the maximum flow from s to t. (a) Prove or disprove the following statements: i. If e is a flow-stopper, then there is a minimum s-t cut that it crosses. ii. If we can find a minimum s-t cut that e crosses, then we know e is a flow-stopper. (b) Design an alogrithm that takes in a graph G (with all of the properites above), a max st flow f for G, and an edge e', and decides if e' is a flow-stopper. Your algorithm should have a runtime of O(|E| - cel), where cel is the capacity of e