Research News, November-December 1998

Previous News Next News

Return to Research News Index

Issue last updated December 13, 1998, 1998.

The Princeton Meeting on Average-Case Analysis of Algorithms

First of all, here is a photograph of the merry band at Princeton, courtesy of Julien Clément.

Click for full image

• From Uwe Roesler, On the analysis of stochastic divide-and-conquer algorithms. This well-motivated paper starts with a perspective on recursive equations on random variables describing the cost of many divide-and-conquer algorithms. There, you'll find a lucid discussion of what is often called the recursive method with emphasis on distributional analyses. (We all know that Roesler, together with Hennequin and Régnier did pioneering work on the distributional analysis of Quicksort). Then, Roesler proceeds to illustrate these ideas by showing the existence of a limit distribution for median-of-(2k+1) Quicksort. Thus, quicksort, median-quicksort, quadtree search (see below), recursive trees (see Fill's paper in our RN07-98 issue), as well as several other comparison-based algorithms are now known to admit limit distributions.
  Uwe Roesler needed the second term in the asymptotic expansion of the mean cost of median-of-(2k+1) Quicksort. He writes (Oct 98): for the expectation, it was a major problem to find the second leading term. The proposed way in my paper is new to my knowledge, and it involves some advanced probabilistic arguments. I know of no analytic tool to do this in this case. I hope this question will inspire people and the Bulletin Board is certainly an adequate place for discussing this point. My own feeling is that, since average-case Quicksort leads to inhomogeneous equations of the Euler type, everything (regarding average-case) can be found analytically. Maybe, this is an overly optimistic view in the specific case at hand?
• Ludger Rueschendorf writes (Oct 98): Here are two recent papers for the AofA pages.The first one on quadtrees is submitted to Random Structures. The second one I have not decided so far. Uwe Roesler and I are just preparing a review on the contraction method.
  • The first of these two papers is On the internal path length of d-dimensional quadtrees. The title says it all. The distribution that has been found thus generalizes that of path length in binary search trees, which is the same as that of quicksort, given a well-known equivalence principle. The quadtree distribution is obtained by recursive/contraction methods. The moments are computable easily and the kth moment involves the values of the zeta function. Large deviation estimates also result from this approach.
  • The second paper is Convergence of two-dimensional branching recursion. It deals with the case of 2x2 matrix recursions as will arise from two divide-and-conquer procedures that call one another. Some examples are worked out using a nice combination of computer algebra and eigenvalue theory. Remember that random products of matrices are a very delicate subject that have been the subject of a vast literature! Consequently, such matrix generalizations are far from being as straightforward as would seem at first glance.

The Barcelona Meeting on Average-Case Analysis of Algorithms, June 14-18, 1999

Philippe Flajolet
Hosam Mahmoud
Helmut Prodinger
Robert Sedgewick
Wojtek Szpankowski
Conrado Martinez (chair and local organizer).

The seminar will be located in the campus of the Universidad Autonoma de Bellaterra (UAB), in the Center for Mathematical Research (Centre de Recerca Matematica, CRM). UAB is about 30 km from Barcelona, but trains and buses run frequently from UAB to Barcelona and vice-versa. Our plan is for all participants to stay at Hotel Campus, within walking distance of the CRM, where we have arranged special discounts for the attendants.

As information on the seminar develops, it will be put on the official web page of the seminar at http://www.lsi.upc.es/~aofa. Stay tuned!

For those who are not familiar with the city, let me add that Barcelona is an absolutely wonderful city with an astoundingly rich and original architecture. The facilities at CRM are very pleasantly organized. Also, it's now a good time to start brushing up your knowledge of the Catalan language!

The lost manuscript of Greene and Knuth

Most of us know the "Purple Book", namely, Greene and Knuth's Mathematics for the Analysis of Algorithms published by Birkhäuser in successive editions since the early 1980's. Here is a new appendix that corresponds to a lost manuscript, as Knuth says, "filed in 1984, forgotten in 1990, found in 1995" that somehow never made its way into the printed book. Suppose you have only half-an-hour to prepare the text of an exam for your grad students. Well, these 24 pages will do (provided none of your students subscribes to this list!).

There you'll find texts (24 pages in toto) of Midterm Exams and Finals at Stanford due to Andy Yao (1984). Clever stuff on

• elementary factorization of recurrences;
• special binary-representation permutations;
• a random sort algorithm;
• sums over primes;
• the "modest" cookie-monster and hashing.

The PhD Thesis of Pascal Hennequin

Get access to Pascal Hennequin's Ph D thesis of which a copy is now stored on these pages. It was defended in 1991, it's in French, and it contains quite a few interesting results.

The Special Issue of Algorithmica on AofA

Philippe Flajolet's Research in Analysis of Algorithms, A Metropolis-Type Optimization Algorithm on the Infinite Tree, Competitive Rank Selection Problem, Packing Random Intervals On-Line, Point Location in Delaunay Triangulations of Random Points, Average-Case Analysis of the Merging Algorithm of Hwang and Lin, The Analysis of Linear Probing Hashing, Saddle Points in Random Matrices: Analysis of Knuth Search Algorithms, Asymptotics of Divide-and-Conquer Recurrences: Batcher's Sorting Algorithm and a Minimum Euclidean Matching Heuristic, The Asymptotic Behavior of the Depth of Tries, Linear Probing and Graphs, Probabilistic Analysis of MULTIPLE QUICK SELECT, Average-Case Analysis for a Simple Compression Algorithm, Average-Case Analysis of Priority Trees: A Structure for Priority Queue Administration, Pattern Frequency Occurrences in a Markovian Sequence, The List Update Problem: Improved Bounds for the Counter Scheme, Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators.

This is 322 pages of great stuff! Here is the table of contents. For subscribers, the journal is accessible at this URL and the particular volume is just at a click.