Layered Network Algorithm) Consider the algorithm described near the end of Section 3.2, which uses phases and augmentations through a layered network.

(a) Provide an algorithm for constructing the layered network of each phase in O(A) time.

(b) Show that the number of augmentations in each phase is at most A, and provide an implementation whereby these augmentations require O(NA) total time.

(c) Show that with each phase, the layer number k(s) of the source node s increases strictly, so that there can be at most N - 1 phases.

(d) Show that with the implementations of (a) and (b), the running time of the algorithm is O(N2A).