Homework 5

Details

Do the following problems from the Algorithms textbook

1. Exercise 7.5. Make sure to clearly write down all of the constraints and the quantity to be minimized/maximized. Also make sure to give the answers to all of the questions asked.
2. Exercise 7.10. For each step, show the augmenting path and the residual network. Show the final flow on the graph and the minimum cut. Please draw the graphs exactly as it is given (i.e. do not move the vertices around).
3. Exercise 7.16. When they say greens they mean lettuce and spinach. Also, if it is not clear, the goal is to minimize energy. Write down the complete linear program and don't forget to cite the Web source(s) you used to solve it. Your solution should specify how many grams of each ingredient should be included and the total energy.
   Note: Be VERY CAREFUL with this, but you may compare your linear program and/or solution with your classmates to make sure you did not make a dumb error. But do not merely copy someone else's solution!