Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 9
- (a)
-
The completion times are
(4, 6, 14, 15).
So, the ACT is (4 + 6 + 14 + 15) / 4) = 9.75.
- (b)
-
When the task order is
2, 1, 4, 3, the completion times are
(2, 6, 7, 15). Now, the ACT is (2 + 6 + 7 + 15) / 4 = 7.5.
- (c)
-
For the greedy order
4, 2, 1, 3, the completion times are
(1, 3, 7, 15). The ACT for this order is 26 / 4 = 6.5.
- (d)
-
The greedy strategy can be implemented in
n log n
time by using an O(n log n) sorting algorithm to first
sort the tasks into ascending order of task time. This sorted order
is the order in which the tasks are to be done.
- (e)
-
Since there are only
n! orders in which the
n tasks can be done,
there must be one with minimum ACT. Let S denote the order that
gives minimum ACT.
Consider the tasks in the order given by S.
Suppose there is an i for which
ti >
ti+1. Let A = t1 + t2 + ... + ti-1.
The ACT of S is
((c1 + ... + ci-1) + ci + ci+1 +
(ci+2 + ... + cn)) / n
= ((c1 + ... + ci-1) + A + ti + A + ti + ti+1 +
(ci+2 + ... + cn)) / n
=
((c1 + ... + ci-1) + 2A + 2ti + ti+1 +
(ci+2 + ... + cn)) / n.
If we swap tasks
i and
i+1, the ACT becomes
((c1 + ... ci-1) + 2A + ti + 2ti+1 +
(ci+2 + ... + cn)) / n.
Since ti >
ti+1, the ACT is reduced as a result of the swap.
So, S does not have minimum ACT. This contradicts the assumption that
S has minimum ACT. So, there can be no
i, in S,
for which
ti >
ti+1. As a result, the tasks in
S are in nondecreasing
order of task times.
When several tasks have the same task time, the relative order of these
does not affect the ACT. So, any sorted order may be used. As a result,
the task order generated by the greedy strategy of (c)
has minmum ACT.