Introduction for SI AofA14

Authors: Mireille BousquetMélou Robert Sedgewick Michèle Soria

Publish Date: 2016/05/12

Volume: 75, Issue: 4, Pages: 577-578

PDF Link

Abstract

Methods that enable precise mathematical analysis of the combinatorial properties of computer programs and data structures have been a focus of a large group of researchers meeting at least annually since the early 1990s The 2014 meeting in Paris was a special one marking the occasion of the first Flajolet Lecture which was delivered by Don Knuth thus honoring two of the field’s pioneersThe first two articles by Drmota and Jin on “An Asymptotic Analysis of Labeled and Unlabeled kTrees” and by Krenn and Wagner on “Compositions into Powers of b Asymptotic Enumeration and Parameters” continue to expand the frontier of combinatorial structures that can be studied with analyticcombinatoric techniques The next three articles address classic problems in the analysis of algorithms In “Analysis of Pivot Sampling in DualPivot Quicksort” Wild finally develops convincing explanation for the success of Yaroslavskiy’s algorithm in practice in “On the Cost of Fixed Partial Match Queries in Kd Trees” Duch Lau and Martinez develop a deeper understanding of the nature of partial match queries and in “A Unified Approach to Linear Probing Hashing with Buckets” Janson and Viola give the first unified presentation of the analysis of linear probing hashing with buckets based on analytic combinatorics In “Asymptotic Lattice Path Enumeration Using Diagonals” Melczer and Mishna develop new results on a fundamental class of problems using multivariate analytic combinatorics and in “Complexity of Anticipated Rejection Algorithms and the DarlingMandelbrot Distribution” Bacher and Sportiello develop a fundamental result about random samplingThe guest editors believe the papers appearing in this issue are representative of current research frontiers in the field Several of them address classical problems with modern analytic tools so they should appeal both to experts in the field and to those interested in current research trends in probabilistic combinatorial and asymptotic methods for the analysis of algorithms

Keywords: