Back to Main Page
Document Version: 1.0, 11/30/2021
How the Quiz Will Be Given and Other Rules
The quizzes will be given on paper and in-class on 12/7/2021. You can try one or both of the quizzes in the class that day. There will only be two possible attempts for these, with the second attempt being he final exam period.
The quizzes will be closed-book, closed-notes, etc. Getting information from any electronic devices is not allowed while taking a quiz. You will sign a pledge on each quiz paper.
It is an honor violation to communicate information about the quiz to anyone who might not have yet taken it.
Topics that might be covered on the Module 9 quiz include:
- Network Flow Problems and Analysis
- Network flow problems
- Augmenting paths
- Dealing with backflow edges, representation of residual graph, etc.
- Ford Fulkerson Algorithm and Analysis
- Ford Fulkerson Correctness
- Max-Flow Min-Cut Theorem
- Minimum Cut, definition of a cut, etc.
- Flow-Value lemma and proof
- Proof of max-flow min-cut theorem.
- Module 9 Homework: Problem 1 is about basic issues and the quiz could have questions like this. Problem 2: not this example, but we might ask why Edmunds-Karp can be better than Ford-Fulkerson. Problem 3: we may ask about augmenting paths and flow in the solution to network-flow graph, but we won’t give you a question like this where it’s hard to come up with a solution quickly.
Topics that might be covered on the Module 10 quiz include:
- Network Flow Reductions
- Edge-disjoint paths and vertex-disjoint paths
- Definition of a reduction
- Bi-partite matching
- Reductions to network flow and relationship between bi-partite matching problems and network flow.
- Circulation Networks
- Circulation Networks with Lower Bounds on edge capacity
- The flight problem given as an example
- Module 10 Homework: could be some questions how to reduce the problem given to another problem you’ve studied
Topics that will not be covered on the quiz include:
- NP Completeness issues or reductions done in class on 11/30