ALGORITHMICA

Volume 22, Number 4, December 1998

Editor-in-Chief: C. K. Wong

Special Issue: Average-Case Analsysis of Algorithms

Guest Editors: Helmut Prodinger and Wojtek Szpankowski

Dedicated to Philippe Flajolet on the occasion of his 50th birthday

Contents:

       363-365
       H. Prodinger, W. Szpankowski
       Preface
 
       366-387
       H. Prodinger, W. Szpankowski
       Philippe Flajolet's Research in Analysis of Algorithms and
       Combinatorics
 
       388-412
       D. Aldous
       A Metropolis-Type Optimization Algorithm on the Infinite Tree
 
       413-447
       F. T. Bruss, M. Drmota, G. Louchard
       The Complete Solution of the Competitive Rank Selection Problem
 
       448-476
       E. G. Coffman, Jr., L. Flatto, P. Jelenkovi\'c, B. Poonen
       Packing Random Intervals On-Line
 
       477-482
       L. Devroye, E. P. Mücke, Binhai Zhu
       A Note on Point Location in Delaunay Triangulations of Random
       Points
 
       483-489
       W. Fernandez de la Vega, A. M. Frieze, M. Santha
       Average-Case Analysis of the Merging Algorithm of Hwang and Lin
 
       490-515
       P. Flajolet, P. Poblete, A. Viola
       On the Analysis of Linear Probing Hashing
 
       516-528
       M. Hofri, P. Jacquet
       Saddle Points in Random Matrices: Analysis of Knuth Search
       Algorithms
 
       529-546
       H. -K. Hwang
       Asymptotics of Divide-and-Conquer Recurrences: Batcher's Sorting
       Algorithm and a Minimum Euclidean Matching Heuristic
 
       547-560
       C. Knessl
       A Note on the Asymptotic Behavior of the Depth of Tries
 
       561-568
       D. E. Knuth
       Linear Probing and Graphs
 
       569-584
       H. M. Mahmoud, R. T. Smythe
       Probabilistic Analysis of MULTIPLE QUICK SELECT
 
       585-599
       D. Merlini, R. Sprugnoli, M. C. Verri
       Average-Case Analysis for a Simple Compression Algorithm
 
       600-630
       A. Panholzer, H. Prodinger
       Average-Case Analysis of Priority Trees: A Structure for Priority
       Queue Administration
 
       631-649
       M. R\'egnier, W. Szpankowski
       On Pattern Frequency Occurrences in a Markovian Sequence
 
       650-659
       H. Shachnai, M. Hofri
       The List Update Problem: Improved Bounds for the Counter Scheme
 
       660-685
       B. Vall\'ee
       Dynamics of the Binary Euclidean Algorithm: Functional Analysis and
       Operators