CSCI 385 Spring 2019
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

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!