Information Technology Reference
In-Depth Information
copy of
Π
∗
,output
c
and redirect the edge to the same vertex in the “one” copy of
Π
∗
as-
sociated with
v
.Incasec),if
v
is the same as the value associated with the current copy of
Π
∗
, produce no output; otherwise also produce no output but redirect the edge to the same
vertex in the “one” copy of
Π
∗
associated with
v
. The new branching program has at most
2
n
+
1copiesof
Π
∗
, thereby increasing its space by an additive term of size
O
(log
n
)
.The
lower bound on
ST
for the sorting problem follows.
The upper bound on
ST
for the sorting problem is obtained by constructing a family of
branching programs, one for each value of
S
. We begin by constructing a “full” branching
program for the case
S
=Θ(
n
)
. Let the variables in the input string be
x
1
,
x
2
,
...
,
x
n
and
let them be tested in sequence. Thus, the root is labeled
x
1
and has
n
successors, each of
which tests
x
2
. There is one successor for each vertex labeled with
x
2
for each way two num-
bers can be chosen with replacement from the set
{
1, 2,
...
,
n
}
. As shown in Problem
10.7
,
there are
N
(
n
,
k
)
ways in which
k
numbers can be drawn from a set of
n
elements with
replacement where the order among the numbers is unimportant and
N
(
n
,
k
)=
n
+
k
−
1
k
Thus,
N
(
n
,1
)=
n
and
N
(
n
,2
)=(
n
+
1
)
n/
2. The successors to vertices labeled
x
2
are
labeled
x
3
.Theyhave
N
(
n
,3
)
successors, and so on. At the
k
th level there are
N
(
n
,
k
)
suc-
cessors. Since
N
(
n
,
k
)
<
2
n
+
k−
1
, it follows that for
k
n
the above branching program
has
O
(
2
2
n
)
vertices or space
S
=Θ(
n
)
. It also has time
T
=
n
and space-time product
O
(
n
2
)
.
To construct a branching program for space
S
=
O
(
n
)
,weuse
O
(
n/S
)
pruned copies
of the full branching program described above. The idea behind the pruning is the fol-
lowing: we scan the input list looking for variables with values in the set
≤
{
1, 2,
...
,
S
}
.If
there are
O
(
S
)
of them, we record the number of values of each type and produce them in
sorted order. However, i f there are more than
O
(
S
)
elements in this range, as we examine
additional inputs we reduce the size of the range so that only
O
(
S
)
space is used to carry
the number of values of variables encountered. (This space is represented by 2
O
(
S
)
vertices
in the branching program.) On each pass through the input either we reduce the size of
the range by
O
(
S
)
or reduce the number of outputs that must be produced by the same
amount. Thus, after 2
n/S
passes the input is sorted. Since each pass tests the value of each
variable, the time is
O
(
n
2
/S
)
.
It is not difficult to convert the above schema into a branching program. The goal is to
have no more than about 2
S
vertices on each level of the branching program. The branching
program will consist of
O
(
n/S
)
copies of the full branching program, each having
n
levels.
Thus, the branching program will have
O
(
n
2
2
S
/S
)
vertices or space
O
(
S
)
.
We order vertices at each level in the branching program, placing those with smaller
input values to the left. We remove vertices at the
j
th level that correspond to input values
larger than
S
as well as those to the right of the first 2
S
vertices on the
j
th level. Each edge
in the first full branching program that is directed into a removed vertex is redirected to the
root of the next copy of the branching program. The second copy of the full branching
program is pruned to remove the vertices appearing in the first copy as well as those reached
on inputs outside the range
[
S
+
1,
S
+
2,
...
,2
S
]
. The edges directed to removed vertices
are redirected to the root of the third copy of the full branching program. A similar process
is applied to each copy of the full branching program.
Search WWH ::
Custom Search