Algorithm Design Techniques
Due: Beginning of class, Tues Nov 6
All questions from the class handout, available in
class or from Perouz.
Late assignments -10% per day, including
Please give late assignments to Perouz (T.A) in McConnell 232
If you work closely with someone else, indicate the person's name(s)
on your homework.
The final write-up of each assignment must, however, be your own work.
1. Handout, problem 7.3.
Write down both the primal and dual LPs. Solve the problem using
lp_solve and give both a primal and dual solution.
2. Handout, problem 7.7. For each of the three outcomes, be sure
to include a certificate of correctness.
Also give an example of each case, complete
with a graph of the constraint region and explanation of the outcome.
3. Handout, problem 7.16.
Use lp_solve to solve the problem. Give the dual solution, and verify
Can you give any interpretation to the dual
Hint: Change the right hand side b-vector in
one component, and see how the optimum solution varies.