Algorithm Design Techniques Fall 2009
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.