------------------------------------------------------------------------------

                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
		      Wednesday, October 23, 1996
                                       
				3:00 pm
                                       
		(Coffee served at 2:30 pm, Room MCS 137)

		              Room MCS 135

------------------------------------------------------------------------------

		    NEW LOWER BOUNDS IN OPTIMAL MERGING

			  Dr. Victor S. Grinberg
			    Robotics Institute
			Carnegie Mellon University
			      5000 Forbes Ave
			 Pittsburgh, PA 15213-3891
			      vsg@cs.cmu.edu

ABSTRACT

Assume 2 ordered chains of elements are given and the goal is to merge them
by means of pairwise comparisons.  This procedure is used as a step in many
sorting algorithms.  Let M(m,n) denote the minimal number of pairwise
comparisons which will suffice to merge 2 chains of lengths m and n in the
worst case.  Upper bounds for M(m,n) correspond to good merging algorithms,
whereas lower bounds set limits for *any* merging algorithm.  In the first
part of the talk we give an outline of the study of the function M(m,n).
Here are some of the steps in this study:

Exact formula for M(2,n) (R. L. Graham, 1969; F. K. Hwang, S. Lin, 1971);
Nontrivial general lower bounds for M(m,n) (D. Knuth, 1973);
Exact formula for M(3,n) (Y. Nissenbaum, 1978; F. K. Hwang, 1980);
Exact formula for the case m=<n=<1.5m (P. K. Stockmeyer, F. F. Yao, 1980);
Exact formula for the case 5m=<n=<7m (C. Christen, 1980);
Exact formula for M(4,n) (S. Monting, 1981); this paper also contained a
conjecture about the exact values of M(5,n), which turned out to be 80% true
(I shall explain this funny statement);
Exact formula for M(5,n) (author, unpublished).

A new recursive lower bound for M(m,n) was obtained by the author.
Combining this lower bound with a known recursive upper bound, the
asymptotic behavior of M(m,n) can be established when m is fixed and n
tends to infinity.

In the second part of the talk we shall consider the *parallel* merging
problem, where non-overlapping comparisons are allowed to be united into
*stages* and performed simultaneously.  In this case we are interested in
P(m,n), the minimal number of stages which will suffice to merge 2 chains
of lengths m and n in the worst case.  A new lower bound for P(m,n) will be
proved.  Combining it with the upper bound, obtained by K.  E. Batcher
(1968), we obtain the following final result: P(m,n)=ceil(log(m+n)) for
all m, n.

MORE FORMAL ABSTRACT ...

This talk consists of 2 independent parts.

1. Let M(m,n) denote the minimal number of pairwise comparisons which 
will suffice to merge 2 chains of lengths m and n in the worst case.

Theorem.  M(m,2n+m-1) >= M(m,n)+m.

Combining this recursive lower bound with a well-known recursive upper
bound M(m,2n+1) <= M(m,n)+m, one can establish the asymptotic behavior of
M(m,n).  Introduce the inverse function n(m,k) = max{i: M(m,i) <= k}.

Corollary.  There exist constants G(m,r) (m = 1, 2, ...; 0 <= r <= m-1) such
that when m is fixed and k -> infinity, n(m,k) ~ G(m, k mod m) 2^(k / m).

Constants G(m,r) are known for m <= 5 due to the work of R.L. Graham,
F.K. Hwang and S. Lin (m=2), Y. Nissenbaum, F.K. Hwang (m=3), J.S. Monting
(m=4), and V.S. Grinberg (m=5).

2. Let T(m,n) denote the minimal delay which occurs in an (m,n) merging
network.  D. Knuth in his ``The Art of Computer Programming'', chapter
5.3.4, exercise 46, asks:

[48] Find an (m,n) merging network with less than ceiling( log(m+n) )
levels of delay or prove that none exists.

The following theorem answers this question.

Theorem. T(m,n) = ceiling( log(m+n) ) for all m, n.

HOST: Prof. David Yates

------------------------------------------------------------------------------
For colloquium info, including directions, see http://www.cs.bu.edu/colloquium
     For more information contact Prof. David Yates <djy@cs.bu.edu>
------------------------------------------------------------------------------