# 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/network-flow/exercises.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.