Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed or not compliant with the specification. Submit your homework via Blackboard as one PDF or Word document. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
1. (25) [Flow network: concepts]
State the key idea that enables the Ford-Fulkerson algorithm to correct a wrong choice of augmenting flow in the flow network.
Given a cut (A, B) in a flow network, (i) define the capacity of the cut and state how it is calculated and (ii) state the condition on edges crossing the cut if the cut is a minimum cut. Give your answers as intuitive statements without using equations.
State the key idea that makes capacity-scaling max-flow algorithm likely to run faster than Ford-Fulkerson max-flow algorithm.
(25) [Flow network: quiz] Textbook Exercise 5 in Chapter 7. If you believe the statement is true, give a convincing (correct and complete) argument. If you believe the statement is false, provide a counterexample and show why it is a counterexample.
