Information Technology Reference
In-Depth Information
The reader is asked to show that the program of Fig.
10.22
can be converted to a branch-
ing program of space
O
(
S
)
and time
O
(
T
)
. (See Problem
10.41
.)
The program of Fig.
10.22
relies on the fact that input variables are drawn from the set
1, 2, 3,
...
,
n
c
{
1, 2, 3,
...
,
n
}
{
}
,
c>
1, the outer loop is executed
O
(
n
c
/S
)
times and its total running time is
O
(
n
c
)
.Thus,
the program is not optimal in this case.
. If the set from which they are drawn is much larger, say
10.13.8 Sorting
The sorting problem is described in Section
6.8
. The general sorting problem is defined by
afunction
f
(
n
)
n
that rearranges the values of input variables so they are in
descending order. Given a branching program for sorting, we show below that a branching
program for the unique-elements problem can be obtained with a small additional amount of
space. As a consequence, the space-time product lower bound for unique elements applies to
the sorting problem. We also give a nearly matching upper bound.
n
sort
:
R
→R
THEOREM
10.13.9
Let
|R| ≥ n
. There is an integer
n
0
>
0
such that for
n ≥ n
0
and
S
=Ω(log
n
)
the time
T
and space
S
used by any general branching program for the sorting
function
f
(
n
)
n
n
sort
:
R
→R
that reports its outputs in descending order must satisfy
ST
=Ω(
n
2
)
This lower bound can be met to within a constant multiplicative factor for inputs drawn from the
set
.
Proof
Given a branching program for
f
(
n
)
sort
{
1, 2, 3,
...
,
n
}
that uses space
S
, we use it to construct a
branching program for
f
(
n
)
unique
that uses space
S
+
O
(log
n
)=
O
(
S
)
.Since
f
(
n
)
unique
requires space that is
Ω(
n
2
/T
)
, the same lower bound applies to sorting.
The branching program for
f
(
n
)
sort
generates its sorted outputs in descending order. By
analyzing the outputs the unique elements can be found. Store the last output
l
along with
abit
b
that is 1 if
l
is so far the only occurrence of this value and 0 otherwise. If the next
output value is the same as
l
,set
b
to 0. If it is different from
l
and
b
=
1, produce
l
as
an output, replace
l
with the last output, and set
b
to 1. Otherwise, do not produce an
output.
Given a branching program
Π
forsorting,wedescribeabranchingprogramforunique
elements that uses modified copies of
Π
. If more than one output appears on some edge
in
Π
,modifyit(yielding
Π
∗
) by replacing edges producing more than one output by a
sequence of edges each producing one output separated by vertices testing an arbitrary in-
put. This increases the number of vertices in
Π
by a factor of at most
n
and adds at most
log
2
n
to its space. Now make 2
additional copies of
Π
∗
, two for each value in
,a
“one” copy if the value is the first encountered in the sorted output and a “zero” copy if it
is not.
Consider an edge in
Π
∗
or one of its copies that produces an output (call it
v
). There
are several cases to examine: the current copy of
Π
∗
is a) the original copy, b) a “one” copy,
or c) a “zero” copy. In case a), redirect the edge to the same vertex in the “one” copy of
Π
∗
associated with
v
.Incaseb),if
v
is different from the value
c
associated with the current
|R|
R
Search WWH ::
Custom Search