Homework: Homework 8. Flow

Assigned

• November 10, 2026

Due

• November 20, 2026 10:00pm

Collaboration

Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\) If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

1. 24.1-1 Show that splitting an edge in a flow network yields an equivalent network

2. 24.1-7 Suppose that a flow network has vertex capacities as well. Show how to convert it into an equivalent flow network without vertex capacities. How many edges and vertices will the new network have?

3. 24.2-5 Prove that adding the supersources and supersinks doesn’t change the flow

4. 24.2-8 No nodes into S does not change FordFulkerson

5. 24.2-11  Edge Connectivity

Bonus. 21.2-4,21.2-5 Course Management: You have m courses, r rooms with capacities. Each room can have at most one course, each course has exactly one TA and Professor. There are p professors with a list of courses that they can teach. Each professor has a list of 5 TAs they will work with. TAs can work in any course but are limited to only working one course. Figure out how to solve this problem, prove it works, and give a runtime analysis.