COSC 320 Assignment 6 Problems
Flow Networks
March 25, 2024
This assignment is due on Friday April 12, 2024 at 10pm Kelowna time on Canvas. Assignments submitted after this deadline, will receive a penalty or won’t be accepted. Please see course outline for details. Please follow these guidelines:
• We strongly recommend that you prepare your solution using LATEX, and submit a pdf file. We will accept solutions that are prepared using other good formatting systems, as long as they are clearly legible. Solutions that are handwritten or difficult to read will receive a grade of zero.
• Whenever possible, keep the solution to a subproblem on a single page, rather than having it span two pages.
• Include in question 1 below the names of each member of your team. You need to form teams, which will be recorded on Canvas. If you want an extra double-check on your identity, include your student number. Reminder: groups should include a maximum of three students; we encourage groups of two.
• Start each problem on a new page, using the same numbering and ordering as this handout.
• Submit the assignment via Canvas. Your group must make a single submission.
• If you include the problem definitions, we would also appreciate it if you could typeset your solutions in blue, as it makes it easier for TAs to find the solutions.
Before we begin, a few notes on pseudocode. Your pseudocode should communicate your algorithm clearly, concisely, correctly, and without irrelevant detail. Reasonable use of plain
English is fine. You should envision your audience as a capable COSC 320 student unfamiliar with the problem you are solving. Don’t include what we consider to be irrelevant detail.
Remember also to justify/explain your answers, unless explicitly indicated otherwise. We understand that gauging how much justification to provide can be tricky. Inevitably, judgment is applied by both student and grader as to how much is enough, or too much, and it’s frustrating for all concerned when judgments don’t align. Justifications/explanations need not be long or formal, but should be clear and specific (referring back to lines of pseudocode, for example).
In this class the words “prove”, “explain”, “show” and “justify” are used interchangeably; we’re not looking for the formality that might be expected in a Math class. You don’t need to be more formal when a proof is requested, but sometimes formal notation or assertions can really help make concepts clear and unambiguous.
On the plus side, if you choose an incorrect answer when selecting an option but your reasoning shows partial understanding, you might get more marks than if no justification is provided.
And the effort you expend in writing down the justification will hopefully help you gain deeper understanding and may well help you converge to the right selection :)
Ok, time to get started...
1 List of names of group members and your group name (as listed on Canvas)
Provide the name of your group and the list here. This is worth 1 mark. Include student numbers as a secondary failsafe if you wish. [1 marks]
2 Statement on collaboration and use of resources
To develop good practices in doing homeworks, citing resources and acknowledging input from others, please complete the following. Answer Yes or No to each question below. This question is worth 1 marks. [1 marks]
1. We used the following resources (list books, online sources, etc. that you consulted):
2. One or more of us consulted with course staff during office hours.
3. One or more of us collaborated with other COSC 320 students; none of us took written notes during our consultations.
If yes, please list their name(s) here:
4. One or more of us collaborated with or consulted others outside of COSC 320; none of us took written notes during our consultations.
If yes, please list their name(s) here:
Figure 1: Flownetwork example
3 Walking to School [8 marks]
Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any block that the other child has stepped on that day. The children have no problem with their paths crossing at a corner. Fortunately, both the professor’s house and the school are on corners, but beyond that he is not sure if it is going to be possible to send both of his children to the same school. The professor has a map of his town. Show how to formulate the problem of determining whether both his children can go to the same school as a maximum-flow problem.
4 Flownetwork [10 marks]
Consider the following flow on a given graph in Figure 1. The notation X:Y means that the edge has flow X out of capacity Y.
1. Consider a cut that contains set S =s, a as one set and T=b, t as another set. What is the flow f(S,T) of this cut? (1 point)
2. What is the capacity of the cut c(S,T) defined in part a? (1 point)
3. Find the residual network of the flow given in this graph. (1 point)
4. Is the current flow at maximum? Answer explicitly. Why? (1 point)
5. If the current flow is not at maximum, find the augmenting path and residual capacity to find a flow which is at maximum (Ford Fulkerson algorithm). (2 points)
6. Draw the graph with the updated flow obtained from part e, if any. (2 points)
7. Draw the residual network of the updated flow from f and explain why the flow cannot
be increased any more. What is the maximum flow of the network? (2 points)
4