CS105 W11: Homework 06

1. CLRS 29.2-3. But also explain what the y values in the dual problem represent. In particular, given a graph with V = {s, x, y, z} and edge weights:
   • (s, x) = 10
   • (s, y) = 7
   • (x,z) = 15
   • (y,z) = 4
   • (y,x) = 2

   Give the linear program, the dual, and the solution to each. (Hint - don't solve the LP using simplex! You can assign values to the x's and the y's based on what they represent, and then can verify that all constraints are met and that the functions maximized and minimized have the same value.)

2. CLRS 29.4-3. The LP describing maximum flow the third edition is closer to the version of flow that we saw in KT (no negative flows), and is probably easier to use than the one in the second edition. Show the LP and the dual on the graph given in the last problem replacing z by t (the sink) and interpreting the edge weights as capacities. Give the solutions to each. (Again, don't use simplex to solve the LP.)

3. CLRS 29-1 b

4. CLRS 5.2-2

5. CLRS 5.2-5

6. CLRS 5.4-6. Express the approximate fraction of the bins that are empty in terms of e. Also give the expected number of bins with exactly k balls. How does this relate to hashing?

7. KT 13.5

1. CLRS 5.4-2

2. CLRS 7-5