Information Technology Reference
In-Depth Information
not available to straight-line programs. As we know from Problem 10.20 , if branching is
allowed but inputs must be read in a data-independent fashion by an input-output-oblivious
finite-state machine, Theorem 10.4.1 applies. Thus, branching programs that read inputs in
a data-independent fashion have no advantage over straight-line programs, at least in terms of
lower bounds on space-time exchanges.
10.10.1 Efficient Branching Programs for Cyclic Shift
We present a branching program for f ( n )
cyclic
that uses space S = O ( logn ) and time T =
;thatis, ST = O ( n log n ) , a product that is much less than the Θ( n 2 ) product
required in the pebble game. (See Section 10.5.2 .)
The function f ( n )
n +
log n
control inputs, and n
“value” inputs whose values are shifted by the amount specified by the control inputs. Our
efficient branching program is a tree program (see Fig. 10.13 ) that reads the control inputs
and selects one of n paths through the tree. (Note that n
cyclic has n +
log n
Boolean variables,
log n
2 log 2 n
2 n .) Each path
corresponds to one of the n possible cyclic shifts of the n value inputs. Attached to a leaf of
this tree is a chain of vertices, one per value input. These inputs appear in the order specified
by the cyclic shift associated with the path. An input value is read and then produced as output
at each of these n vertices. Since this branching program has at most 2 n + 2 n 2 vertices, it has
space O (log n ) . It uses time n +
log n
.
If cyclic shifting is to be done by a straight-line program, say in hardware, then it is better to
use the pebble game for lower bounds since this model applies to logic circuits and the results
it provides are stronger. However, if the problem is to be executed in software, the branching
program should be used unless the program is straight-line.
10.10.2 Efficient Branching Programs for Merging
Consider now the merging problem. In Section 10.5.6 we show that it requires an Ω( n 2 )
space-time product where n is the size of the input. However, when executed by a branching
program it uses space O (log n ) and time O ( n ) ,asweshow.
Figure 10.11 shows a “pyramid” decision branching program to merge two sequences of
length two. It is straightforward to extend this decision branching program to sequences of
length n , as suggested in Fig. 10.16 . In this figure vertices are labeled by the number of
elements that are removed from the two lists being merged before arriving at the vertex carrying
the label. For example, prior to arriving at the vertex labeled ( 2, 1 ) , two elements have been
removed from the left list and one from the right list. We assume that the lists to be merged
each contain n elements. Thus, all the pyramid vertices below a vertex labeled with ( n , k ) or
( k , n ) ,1
1, are deleted because below such vertices no further comparisons are
needed; the outputs produced are those on the list from which k values have been removed.
Thus, we attach a chain of n
k
n
k vertices, one for each of the input values at the end of the
smaller list. If the root is at level 1, vertices labeled ( n , k ) and ( k , n ) are at level n + k + 1
2 n + 1.
The number of vertices on level l of this decision branching program is at most l .Since
2 n , it has at most 2 n + 1
1
l = 1 l =( n + 1 )( 2 n + 1 ) vertices. The space associated with
this program is O (log( n + 1 )( 2 n + 1 )) . Since the length of the longest path in this program
is 2 n , it has time 2 n associated with it. From Lemma 10.9.2 it follows that merging can be
l
Search WWH ::




Custom Search