CSI 4105 Design and Analysis of Algorithms II, Fall 2001
Homework Assignment #3 (100 points, weight 10%)
Due: Thursday, November 29,at 10:00 a.m.(in lecture)
--------------------------------------------------------------------
Question: problem 35-5, page 1051 of the textbook:
Parallel Machine Scheduling (an approximation algorithm)
Mark's breakdown:
part a) 10 marks
part b) 20 marks
part c) 40 marks
You must analyse your algorithm, and not simply say
"it runs in polynomial time".
Marks will be given for the efficiency of the algorithm
you design.
part d) 30 marks
--------------------------------------------------------------------