Chapter 10: Algorithm Design Techniques
10.1 First, we show that if N
O
evenly divides P
O
, then each of
P
j
O
(i
O
−1)P
O
+1
through
P
j
iP
O
must be
placed as the i
O
th
O
job on some processor. Suppose otherwise. Then in the supposed
optimal ordering, we must be able to find some jobs
P
j
x
O
and
P
j
y
O
such that
P
j
x
O
is the t
O
th
O
job
on some processor and
P
j
y
O
is the t
O
+1
th
O
job on some processor but t
x
O
> t
y
O
. Let
P
j
z
O
be the
job immediately following
P
j
x
O
. If we swap
P
j
y
O
and
P
j
z
O
, it is easy to check that the mean pro-
cessing time is unchanged and thus still optimal. But now
P
j
y
O
follows
P
j
x
O
, which is impos-
sible because we know that the jobs on any processor must be in sorted order from the
results of the one processor case.
Let
P
j
e
O
1
,
P
j
e
O
2
, ...,
P
j
eM
O
be the extra jobs if N
O
does not evenly divide P
O
. It is easy to see that
the processing time for these jobs depends only on how quickly they can be scheduled,
and that they must be the last scheduled job on some processor. It is easy to see that the
first M
O
processors must have jobs
P
j
O
(i
O
−1)P
O
+1
through
P
j
iP
O
+M
O
; we leave the details to the
reader.
10.3
,
4 7 8 9
0
1 5
sp
nl
3 :
6 2
10.4 One method is to generate code that can be evaluated by a stack machine. The two opera-
tions are Push
O
(the one node tree corresponding to) a symbol onto a stack and Combine,
O
which pops two trees off the stack, merges them, and pushes the result back on. For the
example in the text, the stack instructions are Push(s), Push(nl), Combine, Push(t), Com-
bine, Push(a), Combine, Push(e), Combine, Push(i), Push (sp), Combine, Combine.
By encoding a Combine
O
with a 0 and a Push
O
with a 1 followed by the symbol, the total
extra space is 2N
O
− 1 bits if all the symbols are of equal length. Generating the stack
machine code can be done with a simple recursive procedure and is left to the reader.
10.6 Maintain two queues, Q
O
1
and Q
O
2
. Q
O
1
will store single-node trees in sorted order, and Q
O
2
will store multinode trees in sorted order. Place the initial single-node trees on Q
O
1
,
enqueueing the smallest weight tree first. Initially, Q
O
2
is empty. Examine the first two
entries of each of Q
O
1
and Q
O
2
, and dequeue the two smallest. (This requires an easily
implemented extension to the ADT.) Merge the tree and place the result at the end of Q
O
2
.
Continue this step until Q
O
1
is empty and only one tree is left in Q
O
2
.
-54-
