Information Technology Reference
In-Depth Information
BRANCHING PROGRAMS
10.35 Give a proof of Lemma
10.9.1
by a) designing a general branching program to simulate
a comparison operator and b) using this design in a complete branching program that
simulates a decision branching program.
10.36 In Section
10.9
a procedure is given to convert a general branching program to a tree
program without increasing the length of any path. Use this fact to show that every
decision branching program with queries
that sorts a list of
n
items requires
worst-case time of at least
(
n/
2
)log(
n/
2
)
when
n
is even. Show that this lower bound
can be achieved up to a constant multiplicative factor.
Hint:
Show that every binary tree with
m
leaves must have a longest path of length
at least
log
2
m
and determine the number of distinct leaves necessary in every decision
branching program for sorting.
{≤
,
=
}
THE BORODIN-COOK LOWER-BOUND METHOD
10.37 The computation time of a branching program is the length of the longest path in its
directed acyclic multigraph. Assume that a
pro
bability is assigned to each input
x
of
length
n
.The
average computation time
,
T
, of a branching program is the sum of
the lengths of the paths associated with different inputs weighted by the probabilities of
these inputs. To compute the average space of a branching program with
k
vertices, the
integers in the set
are assigned to the vertices of the branching program.
The space associated with input
x
is the base-2 logarithm of the largest such integer
encountered during the computation associated with
x
. The average space associat
ed
with a numbering of vertices is the average of this logarithm. The
average space
,
S
,
associated with a branching program is the smallest average space over all numberings
of vertices.
Given a probability distribution on inputs of length
n
,let
C
f
(
a
,
b
)
denote the maxi-
mum over all those tree branching programs of depth
a
of the probability that
b
of the
m
outputs of the function
f
are computed correctly. Show that Theorem
10.11.1
can
be genera
liz
ed to the above probabilistic setting.
Hint:
If
T
is the a
ve
rage time of the branching program
P
, truncate the branching
program at depth 2
T
, call the new program
P
∗
,andshowthat
P
∗
solves the problem
solved by
P
with probability at least 1/2. Also, show that with probability at least 1
/
2
there exists a rich path in some stage that produces
b
=
{
1, 2,
...
,
k
}
outputs. Let
p
i
be
the probability that the subtree with root
i
in some stage correctly produces
b
outputs.
Now develop an upper bound in terms of the
p
i
on the probability that some tree in
some stage correctly produces
b
outputs.
m/σ
APPLICATIONS OF THE BORODIN-COOK LOWER BOUND
10.38 Show that the branching program in Fig.
10.20
computes the inner product of two 3-
element sequences over the
set of integers modulo-2
; that is, the integers
{
}
with
the
EXCLUSIVE
-
OR
function for addition and the
AND
function for multiplication.
10.39 Complete the proof of Theorem
10.13.2
by filling in the details of the construction of
a branching program for integer multiplication for the middle range of space.
0, 1
Search WWH ::
Custom Search