Algorithm Design Techniques     Fall 2009

COMP-360              Assignment 2           Due: Mon October 5, 5pm


Late assignments  -10% per day, final deadline is October 9, 5pm.
Please leave assignments in the drop off box, Trottier 3rd floor.
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. You are given n jobs with processing times t(i), i=1,...,n and two identical processors each of which can handle one job at a time. You wish to schedule each of the jobs on to one of the two machines to minimize the time when all of the jobs are finished.

(a) Show how to formulate this as a Knapsack problem.
(b) Use the dynamic programming technique of section 6.4 to solve the problem with n=10 given by the processing times
94, 98, 153, 146, 76, 132, 73, 55, 62, 169.  (I would write a program rather than do it by hand .....)

Note: If you write a program, submit a listing of the source code. Any programming language is fine.
If you do it by hand, explain how you did it  without having to write out the whole table.


2. (DP) Text, P. 314, problem 3.

3. (DP) Text, P.323, problem 12.
______________________________________________________________________________________________________________________________

4. (Network Flow) Text, P 417, problem 7.
Replace the last paragraph of the question with the following:
(a) Formulate this problem as a network flow problem.
(b) Construct an example where it is not possible to connect every client simultaneously, with the following parameters:
      n=10 clients, 4 base stations and load L=3. Show the max flow in the corresponding network, and the min cut.