Information Technology Reference
In-Depth Information
x
1
x
2
x
3
x
4
x
5
x
6
x
7
Figure 6.13
A bitonic sorter on seven inputs.
MERGING AND SORTING
6.28 Prove Theorem
6.8.3
.
6.29 Show that the recurrences given below and stated in the proof of Theorem
6.8.2
have
the solutions shown, where
C
(
0
)=
1and
D
(
0
)=
1:
1
)+
2
k
=(
k
+
1
)
2
k
C
(
k
)=
2
C
(
k
−
D
(
k
)=
D
(
k
−
1
)+
1
=
k
+
1
6.30 A sequence
(
x
1
,
x
2
,
...
,
x
n
)
is
bitonic
if there is an integer 0
≤
k
≤
n
such that
x
1
> ...> x
k
≤
x
n
.
a) Show that a bitonic sorting network can be constructed as follows: i) sort
(
x
1
,
x
3
,
x
5
,
...
)
and
(
x
2
,
x
4
,
x
6
,
...
)
in bitonic sorters whose lines are interleaved, ii)
compare and interchange the outputs in pairs, beginning with the least significant
pairs. (See Fig.
6.13
.)
b) Show that two ordered lists can be merged with a bitonic sorter and that an
n
-sorter
can be constructed from bitonic sorters.
c) Determine the number of comparators in a 2
k
-sorter based on merging with bitonic
sorters.
...
≤
Chapter Notes
The bulk of this chapter concerns matrix computations, a topic with a long history. Many
topics have been written on this subject to which the interested reader may refer. (See [
25
],
[44], [105], [198], and [362].)
Among the more important recent results in this area are the matrix multiplication algo-
rithm of Strassen [
319
]. Many other improvements have been made on this work, among the
most significant of which is the demonstration by Coppersmith and Winograd [
81
]thattwo
n
n
matrices can be multiplied with
O
(
n
2
.
376
)
ring operations.
The relationships between transitive closure and matrix multiplication embodied in Theo-
rems
6.4.2
and
6.4.3
as well as the generalization of these results to closed semirings are taken
from the topic by Aho, Hopcroft, and Ullman [
10
].
×
Search WWH ::
Custom Search