CS 4349.003. Advanced Algorithm Design and Analysis Spring 2017 Assignment 7 Thu, Apr 20 You can write or type your answers. Submit in class or upload on elearning. Due: 1:00 PM, Thu, April 27 1. Ex. 26.2-3 (p. 730). Edmonds-Karp algorithm on Fig 26.1(a). 2. Ex. 26.1-7 (p. 714). Flow with vertex capacities. Optional problems (for extra credit): A. Suppose an algorithm for finding a maximum flow has been run, and you have the flow value through each edge. It is suspected that the program has a bug, and so the output may be wrong. Write an efficient function to verify that the flow is valid, and is actually a maximum flow of the graph. Your function should also print a minimum (S,T)-cut that is used in the proof of the maxflow-mincut theorem. What is its running time? Prototype: boolean verifyMaxFlow(G, s, t, c, f). B. Problem 26-1 (p. 760-761). Escape problem.