hide
Free keywords:
-
Abstract:
We study fundamental comparison problems on
strings of characters, equipped with the usual
lexicographical ordering.
For each problem studied, we give a parallel algorithm
that is optimal with respect to at least one
criterion for which no optimal
algorithm was previously known.
Specifically, our main results are:
%
\begin{itemize}
\item Two sorted sequences of strings, containing
altogether $n$~characters, can be merged in
$O(\log n)$ time using $O(n)$ operations
on an EREW PRAM.
This is optimal as regards both the running time
and the number of operations.
\item A sequence of strings, containing altogether
$n$~characters represented by integers of size
polynomial in~$n$, can be sorted
in $O({{\log n}/{\log\log n}})$ time
using $O(n\log\log n)$ operations on
a CRCW PRAM.
The running time is optimal for any
polynomial number of processors.
\item The minimum string in a sequence of strings
containing altogether $n$ characters can be
found using (expected) $O(n)$ operations in
constant expected time on a randomized
CRCW PRAM, in $O(\log\log n)$ time on a
deterministic CRCW PRAM with a program depending on~$n$,
in $O((\log\log n)^3)$ time on a
deterministic CRCW PRAM with a program
not depending on~$n$,
in $O(\log n)$ expected time on a randomized
EREW PRAM, and in $O(\log n\log\log n)$ time
on a deterministic EREW PRAM.
The number of operations is optimal, and
the running time is optimal for the randomized algorithms
and, if the number of processors is limited to~$n$,
for the nonuniform deterministic CRCW
PRAM algorithm as wel
