CS 170 Reading Quiz -- Week 11, Monday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

1. Consider the graph shown below:

The numbers represent the capacity of each edge. (For instance, the graph indicates that we can send up to 2 units of flow along the edge from vertex s to vertex a.) What is the value of the largest flow from s to t?

2. Write a linear program whose solution is the value of the maximum flow from s to t in the graph above.

In particular, let the variable x_sa represent the number of units of flow sent along the edge from vertex s to vertex a; the variable x_sb represent the number of units of flow sent along the edge from vertex s to vertex b; and so on. Then, write down the set of constraints (inequalities and/or equalities) as well as the objective function to minimize/maximize.

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page