> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/network-flow/exercises.md).

# 9.3. Quiz

## Augmenting Paths

An augmenting path is a directed path between the source and target vertices; no need to worry about residuals for this quiz.

* Create the [`NetworkFlowQuiz`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/flow/NetworkFlowQuiz.java) class under the [`graph.flow`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/flow/) package.
* Update the `getAugmentingPaths()` method that returns all augmenting paths between the specific source and target vertices using depth-first traverse.

## Extra Credit

* Create the `NetworkFlowQuizExtra` class and update the `getAugmentingPaths()` method such that it uses breadth-first traverse instead of depth-first traverse.

## Simplex Algorithm

Given the following graph where there are two source vertices, $$S\_1$$and $$S\_2$$, and two target vertices, $$T\_1$$ and $$T\_2$$, define the objective functions and their constraints to find the (1) max-flow and (2) min-cut using the simplex algorithm:

![](/files/-MMH7I3pox6DUfLZ7nw2)

## Report

Write `quiz8` that includes:

* The worst-case complexity of your `getAugmentingPaths()` method.
* An explanation of when the depth-first traverse is preferred over the breadth-first traverse and vice versa to find augmenting paths.
* An objective function and is constraints to find max-flow.
* An objective function and is constraints to find min-cut.