Notes:

• Algorithms should be given in pseudocode. Please try to avoid relying on features of particular programming languages that would be unfamiliar to readers unfamiliar with that programming language (for example, negative indices in Python or the Python itertools library).
• For this class is is generally not necessary to validate input in your pseudocode: if a problem says the input will be in a certain form then write your pseudocode under the assumption that the input is in that form.
• "Find/devise/give an efficient algorithm" means "find an algorithm that is as efficient as possible, and you have to figure out for yourself whether your solution can be improved."
• Note that you can view source to see the LaTeX source for most of the formulas.

Problem : Complete the Canvas quizzes on maximum flow/minimum cut. (These may have different due dates.)

Problem : Suppose that to build a single electric car we need a three-person team consisting of a machinist, a welder, and an electrician. We have a pool of $k$ machinists, $m$ welders, and $n$ electricians. Each tradesperson can be assigned to at most one team. Some pairs of machinists and welders refuse to work together, and some pairs of welders and electricians refuse to work together (the machinists and electricians do not work on the cars at the same time, so their personal squabbles are irrelevant). Describe a polynomial-time algorithm to determine the maximum number of teams we can form given the constraints on who will work with whom and prove that it is correct (hint: if you can solve the problem by creating an appropriate input to a standard algorithm then you need only prove that input correctly models the problem). Explain why the running time of your algorithm is polynomial in $k$, $n$, and $m$.

Problem : Tardos and Kleinberg, Ch. 7, Ex. 11 (if you don't have backward edges in the residual graph then you can't guarantee that you find any fraction $\frac{1}{b}$ of the maximum flow for any $b > 1$). Be sure to include

• an explanation of what the maximum flow in your graph is;
• a sequence of paths that, if chosen by Ford-Fulkerson, leads to non-optimal flow;
• an explanation of why there are no more paths of positive residual capacity after that sequence of paths when you omit backward edges from the residual graph; and
• an explanation of how to generalize the above so that you end up with an arbitrarily small ratio of found flow to maximum flow.