Homework 2 (assigned January 17, due January 23)

Reading: CLRS chapter 26, sections 26.1–26.3.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

"Do" Exercises (not to be handed in):

1. Exercise 26.1-6, page 714.

2. Exercise 26.2-6, page 730.

3. Exercise 26.2-11, page 731.

4. Exercise 26.3-1, page 735.

5. Exercise 26.3-3, page 735.

6. Exercise 26.3-4, page 735.

7. Problem 26-5, pages 762–763.

Assigned Problems (to be handed in):

• For each problem that requires you to write an algorithm, give an English description of your algorithm, describe your algorithm in pseudocode, analyze its running time, and argue for its correctness. Your argument should be precise, i.e., rigorous enough to be converted to a formal argument if required.
• When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.

1. Problem 26-1, page 760–761.
   • part a. (2 points)
   • part b, write pseudocode (10 points); argue that your algorithm is correct (2 points); analyze its running time (1 point).

2. Problem 26-2, page 761.
   • part a, write pseudocode (8 points); argue for correctness (2 points); analyze the running time (1 point).
   • part b, explain your answer. (4 points)

3. Problem 26-4, page 762. For each part, write pseudocode, explain your algorithm, and justify its O(V + E) running time. (5 points for each part)

4. Consider an arbitrary directed network (G = (V, E), s, t, capacities c: V × V → R⁺) in which we want to find the maximum flow. Assume for simplicity that all edge capacities are at least 1, and define the capacity of an s-to-t path to be the smallest capacity of its constituent edges, c(p) = min{c(u, v): (u, v) is an edge in p}. The fattest path from s to t is the path with the largest capacity c(p).
   • Show that the fattest s-to-t path in a directed network can be computed by a variant of Dijkstra's algorithm.
     • Describe your algorithm in pseudocode. (4 points)
     • Argue for the correctness of your algorithm. (2 points)
     • Analyze the running time of your algorithm. (1 point)
   • Show that the maximum flow in G is the sum of individual flows along at most |E| paths from s to t. (4 points)
   • Now show that if we always increase flow along the fattest path in the residual graph, the Ford-Fulkerson algorithm will terminate in at most O(E log| f |) iterations, where | f | is the size (value) of the maximum flow. (4 points)

5. You are given a directed graph G = (V, E), with a source s ∈ V and sink t ∈ V, and nonnegative numbers l(u, v) for each edge (u, v) ∈ E. We define a flow f, and the value of a flow as usual, requiring that all vertices except s and t satisfy flow conservation. However, the given numbers l are lower bounds on the edge flow: i.e., they require that  f (u, v) ≥ l(u, v) for each edge (u, v) ∈ E, and there is no upper bound on flow values on the edges. We call an s-to-t flow f feasible if and only if  f (u, v) ≥ l(u, v) for every edge (u, v). A natural problem in this setting is to find a feasible s-to-t flow of minimum value.
   • Describe an efficient algorithm to compute a feasible s-to-t flow, given the directed graph G = (V, E), the nonnegative numbers l(u, v) for each edge (u, v), and the vertices s and t as input.
     • Describe your algorithm in pseudocode. (8 points)
     • Explain how your algorithm works. (1 point)
     • Analyze the running time of your algorithm. (1 point)
   • Suppose you have a subroutine called MaxFlow that computes maximum flows in networks with edge capacities. Describe an efficient algorithm to compute a minimum flow in a given network with lower bounds l(u, v) on the edges. Your algorithm should call MaxFlow exactly once.
     • Describe your algorithm in pseudocode. (4 points)
     • Analyze the running time of your algorithm. (1 point)
   • State an analogue of the max-flow min-cut theorem for this problem. Prove your theorem (or argue that it is correct). Do minimum flows correspond to maximum cuts? Explain. (5 points)