Home

Please send all comments directly to Mark Daniel Ward: mdw@purdue.edu

*************************************************************************************************************

Volume I (Analytic Combinatorics) editor: Bob Sedgewick

Chapter 1 on Analytic Combinatorics: (Bob Sedgewick)

[47] Elements of a general theory of combinatorial structures.

[63] Mathematical tools for automatic program analysis. (First portion only. Second portion is subsumed by [47].)

[69] Mathematical methods in the analysis of algorithms and data structures.

[(99)70] L'analyse d'algorithmes ou le risque calculé.

[72] Random tree models in the analysis of algorithms.

[91] Average-case analysis of algorithms and data structures.

[95] The cycle construction.

[97] Analytic analysis of algorithms.

[171] Singular combinatorics.

[189] A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics.

[192] Analytic combinatorics---a calculus of discrete structures.

Secondary papers [not yet confirmed]

From Random Generation and Simulation (Vol VI): [179,194]

Volume I, Chapter 2, on Singularity Analysis: (Andrew Odlyzko)

[86] Singularity analysis of generating functions.

[117] Search costs in quadtrees and singularity perturbation asymptotics.

[148] Singularity analysis and asymptotics of Bernoulli sums.

[150] On Stirling numbers for complex arguments and Hankel contours.

[182] Singularity analysis, Hadamard products, and tree recurrences.

*************************************************************************************************************

Volume II (Limit Laws and Dynamical Systems) editor: Brigitte Vallée

Chapter 1 on Gaussian Limit Laws: (H.K. Hwang -- draft of Chapter Introduction)

[45] Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations.

[88] Gaussian limiting distributions for the number of components in combinatorial structures.

[96] Varieties of increasing trees.

[112] General combinatorial schemas: Gaussian limit distributions and exponential tails.

[144] Continued fraction algorithms, functional operators, and structure constants.

[159] Analytic variations on bucket selection and sorting.

[198] Isomorphism and symmetries in random phylogenetic trees.

Secondary papers

From Text (Vol III): [191]

Volume II, Chapter 2, on Airy Function: (Cyril Banderier and Guy Louchard -- draft of Chapter Introduction)

[142] On the analysis of linear probing hashing.

[(152)160] Random maps, coalescing saddles, singularity analysis, and Airy phenomena.

[165] Analytic variations on the Airy distribution.

[175] Hachage, arbres, chemins & graphes.

[181] Airy phenomena and analytic combinatorics of connected graphs.

Secondary papers [not yet confirmed]

From Random Generation and Simulation (Vol VI): [179,194]

Volume II, Chapter 3, on Dynamical Systems: (Brigitte Vallée -- draft of Chapter Introduction)

[90] The lattice reduction algorithm of Gauss: an average case analysis.

[(114)132] An average-case analysis of the Gaussian algorithm for lattice reduction.

[140] The analysis of hybrid trie structures.

[157] Continued fractions, comparison algorithms, and fine structure constants.

[161] Dynamical sources in information theory: A general analysis of trie structures.

[202] The number of symbol comparisons in QuickSort and QuickSelect.

[208] Digital trees and memoryless sources: from arithmetics to analysis.

[U01] On the Gauss-Kuzmin-Wirsing constant

Secondary papers:

From Protocols (Vol III): [55]

From Hashing (Vol IV): [37]

From Tries (Vol III) : [187]

From Mellin (Vol III) [120]

From Gaussian laws (Vol II): [144]

*************************************************************************************************************

Volume III (Text, Information Theory, and the Mellin Transform) editor: Wojciech Szpankowski

Chapter 1 on Text: (see pages 3--8: Pierre Nicodème -- draft of Chapter Introduction)

[74] Deviations from uniformity in random strings

[76] Discrepancy of sequences in discrete spaces

[(151)174] Motif statistics

[(164)191] Hidden word statistics

Secondary papers [not yet confirmed]

From Dynamical Systems (Vol II) : [161,202]

Volume III, Chapter 2 on Information Theory: (see pages 17--25: Wojciech Szpankowski -- draft of Chapter Introduction)

[158] Data compression via binary decision diagrams.

[(156)173] Analytic variations on redundancy rates of renewal processes.

Volume III, Chapter 3 on Tries & digital search trees: (see pages 37--44: Julien Clément and Mark Daniel Ward -- draft of Chapter Introduction)

[34] A recursive partitioning process of computer science

[39] Methods in the analysis of algorithms: Evaluations of a recursive partitioning process

[53] Algebraic methods for trie statistics

[61] Digital search trees revisited

[187] The ubiquitous digital tree

Secondary papers [not yet confirmed]

From Dynamical Systems (Vol II) : [140,161,208]

From Random Generation and Simulation (Vol VI): [60]

Volume III, Chapter 4 on Mellin Transform: (see pages 49--57: Philippe Dumas -- draft of Chapter Introduction)

[(41)58] Partial match retrieval of multidimensional data

[52] Some uses of the Mellin integral transform in the analysis of algorithms.

[101] Generalized digital trees and their difference-differential equations

[120] Mellin transforms and asymptotics: Harmonic sums.

[124] Mellin transforms and asymptotics: Finite differences and Rice's integrals.

[125] Asymptotique des récurrences mahlériennes : le cas cyclotomique.

[129] The average case analysis of algorithms: Mellin transform asymptotics.

Secondary papers [not yet confirmed]

From Random Generation and Simulation (Vol VI): [200]

Volume III, Chapter 5 on Divide & Conquer and the Mellin-Perron Formula: (see pages 63--69: Mordecai Golin -- draft of Chapter Introduction)

[(105)115] Mellin transforms and asymptotics: The mergesort recurrence.

[116] Mellin transforms and asymptotics: digital sums.

[199] Multidimensional divide-and-conquer and weighted digital sums (extended abstract).

Volume III, Chapter 6 on Protocols: (see pages 75--88: Philippe Jacquet -- draft of Chapter Introduction)

[49] Analysis of a stack algorithm for random multiple-access communication.

[54] Q-ary collision resolution algorithms in random-access systems with free or blocked channel access.

[55] On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel.

[65] Analytic models for tree communication protocols.

[68] Estimating the multiplicities of conflicts to speed their resolution in multiple access channels.

[(71)P03] Évaluation de protocoles de communication : aspects mathématiques.

Secondary papers [not yet confirmed]

From Dynamical Systems (Vol II) : [208]

*************************************************************************************************************

Volume IV (Combinatorial Structures -- Trees and Graphs) editor: Michèle Soria

Chapter 1 on Term trees: (Jean-Marc Steyaert)

[4] A class of non-recursive sorting algorithms.

[15] Analyse en moyenne de la détection des arbres partiels.

[28] On the analysis of tree-matching algorithms.

[43] Patterns and pattern-matching in trees: An analysis.

[66] Level number sequences for trees.

[89] Analytic variations on the common subexpression problem.

[177] And/Or trees revisited.

Volume IV, Chapter 2 on Height of trees: (Nicolas Broutin and Luc Devroye)

[(26)33] The average height of binary trees and other simple trees.

[104] The distribution of heights of binary trees and other simple trees.

[(195)206] The distribution of height and diameter in random non-plane binary trees

Volume IV, Chapter 3 on Search Trees: (Conrado Martinez)

[51] Search trees and bubble memories.

[75] Analysis of kdt-trees: kd-trees improved by local reorganisations.

[(81)82] Average cost of orthogonal range queries in multiattribute trees.

[103] Page usage in a quadtree index.

[(93)106] Analytic variations on quadtrees.

[122] Hypergeometrics and the cost structure of quadtrees.

[135] Patterns in random binary search trees.

Secondary papers [not yet confirmed]

From Dynamical Systems (Vol II) : [202]

Volume IV, Chapter 4 on Hashing: (Alfredo Viola -- draft of Chapter Introduction)

[36] A branching process arising in dynamic hashing, trie searching and polynomial factorization.

[37] On the performance evaluation of extendible hashing and trie searching.

[121] On Ramanujan's Q-function.

Volume IV, Chapter 5 on Random Graphs, Mappings, Maps: (Marc Noy and Gilles Schaeffer)

[78] The first cycles in an evolving graph.

[85] Random mapping statistics.

[147] Properties of random triangulations and trees.

[149] Analytic combinatorics of non-crossing configurations.

[155] Analytic combinatorics of chord diagrams.

[(154)172] On the robustness of interconnections in random graphs: a symbolic approach.

Secondary papers [not yet confirmed]

From Random Generation and Simulation (Vol VI): [179,194]

*************************************************************************************************************

Volume V (Combinatorial Structures) editor: H.K. Hwang

Chapter 1 on Languages: (Cyril Nicaud and Frédérique Bassino -- draft of Chapter Introduction)

[62] Prefixes of infinite words and ambiguous context-free languages.

[(46)64] Analytic models and ambiguity of context-free languages.

[83] Algebraically independent formal power series: A language theory interpretation.

[(73)100] Birthday paradox, coupon collectors, caching algorithms and self-organizing search.

Volume V, Chapter 2 on Polynomials: (Daniel Panario -- draft of Chapter Introduction)

[107] Sur une famille de polynômes issus de l'analyse numérique.

[145] An analytic approach to smooth polynomials over finite fields.

[(127)163] The complete analysis of a polynomial factorization algorithm over finite fields.

Volume V, Chapter 3 on Continued Fractions: (Xavier Viennot -- draft of Chapter Introduction)

[14] Analyse d'algorithmes de manipulation de fichiers.

[19] Computing integrated costs of sequences of operations with application to dictionaries.

[21] Dynamic data structures: finite files, limiting profiles and variance analysis.

[(22)23] Combinatorial aspects of continued fractions.

[24] Structures de données dynamiques en réservoir borné

[(18)25] Sequence of operations analysis for dynamic data structures.

[30] Analyse de structures de données dynamiques et histoires de fichiers.

[32] On congruences and continued fractions for some classical combinatorial quantities.

[59] The analysis of simple list structures.

[77] Elliptic functions, continued fractions and doubled permutations.

[87] Non-overlapping partitions, continued fractions, Bessel functions and a divergent series.

[153] The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions.

[186] The Fermat cubic, elliptic functions, continued fractions, and a combinatorial excursion.

[203] Pseudo-factorials, elliptic functions, and continued fractions.

[205] Combinatorial Models of Creation-Annihilation

[C03], Merry Christmas card for 2008

[C01], Happy New Year card for 2009

[C02], Happy New Year card for 2010

Volume V, Chapter 4 on Random Walks; Lattice Paths: (Mireille Bousquet-Mélou -- draft of Chapter Introduction)

[56] The evolution of two stacks in bounded space and random walks in a triangle.

[92] Pólya festoons.

[141] The maximum of a random walk and its application to rectangle packing.

[(146)167] Generating functions for generating trees.

[168] Basic analytic combinatorics of directed lattice paths.

[P06] The enumeration of prudent polygons by area and its unusual asymptotics

[P09] Some new self-avoiding walk and polygon models

Volume V, Chapter 5 on Urns: (Nicolas Pouyanne and Basile Morcrette -- draft of Chapter Introduction)

[183] Analytic urns.

[188] Some exactly solvable models of urn process theory.

[196] Analytic combinatorics of the Mabinogion urn.

Volume V, Chapter 6 on Number Theory: (Michael Drmota -- draft of Chapter Introduction)

[143] Euler sums and contour integral representations.

[197] On differences of zeta values.

[U02] Zeta function expansions of classical constants

Secondary papers [not yet confirmed]

From Dynamical Systems (Vol II) : [90,(114)132,157]

From Gaussian laws (Vol II): [144]

Volume V, Chapter 7 on Register Function: (Helmut Prodinger -- draft of Chapter Introduction)

[17] Deux problèmes d'analyse d'algorithmes.

[(13)20] The number of registers required for evaluating arithmetic expressions.

[27] A note on Gray code and odd-even merge.

[57] Register allocation for unary-binary trees.

*************************************************************************************************************

Volume VI (Effective methods) editor: Bruno Salvy

Chapter 1 on Computer Algebra: (Bruno Salvy -- draft of Chapter Introduction)

[109] A finite sum of products of binomial coefficients.

[123] Computer algebra libraries for combinatorial structures.

[136] The SIGSAM challenges: symbolic asymptotics in practice.

[184] On the non-holonomic character of logarithms, powers, and the $n$th prime function.

[185] Fast computation of special resultants.

[207] Lindelöf representations and (non-)holonomic sequences.

Volume VI, Chapter 2 on Automatic Analysis: (Paul Zimmermann -- draft of Chapter Introduction)

[35] Élements d'un calcul de complexité de programmes récursifs d'arbres.

[(31)67] A complexity calculus for recursive tree algorithms.

[79] Lambda-Upsilon-Omega: An assistant algorithms analyzer.

[80] Lambda-Upsilon-Omega: The 1989 CookBook.

[94] Automatic average-case analysis of algorithms.

Secondary papers [not yet confirmed]

From Random Generation and Simulation (Vol VI): [179,194]

Volume VI, Chapter 3 on Random Generation and Simulation: (Philippe Duchon and Michèle Soria -- draft of Chapter Introduction)

[(42)60] The complexity of generating an exponentially distributed variate.

[(113)119] A calculus for the random generation of labelled combinatorial structures.

[(170)179] Boltzmann samplers for the random generation of combinatorial structures.

[194] Boltzmann sampling of unlabelled structures.

[200] On Buffon machines and numbers.

Secondary papers:

From Analytic Combinatorics (Vol I ): [171, 192]

From Airy Function (Vol II) : [181]

From Tries (Vol III): [53,61,187]

From Mellin (Vol III): [120]

From Random Graphs, Mappings, Maps (Vol IV): [85,149]

From Automatic analysis (Vol VI) : [94,35]

From Approx. Counting (Vol VI): [134,180]

Volume VI, Chapter 4 on Approx. Counting: (Jérémie Lumbroso -- draft of Chapter Introduction)

[(38)48] Approximate counting: A detailed analysis.

[(40)50] Probabilistic counting algorithms for data base applications.

[84] On adaptive sampling.

[134] Adaptive sampling.

[176] Loglog counting of large cardinalities.

[180] Counting by coin tossings.

[193] Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.

Secondary papers [not yet confirmed]

From Random Generation and Simulation (Vol VI): [200]

*************************************************************************************************************

Volume VII, editors: Bruno Salvy, Michèle Soria, Brigitte Vallée

Volume VII, Chapter 1

[3] Une formalisation de la notion d'algorithme de tri non récurrent (Ph.D. thesis, 1972)

Volume VII, Chapter 2

[(16)29] Analyse d'algorithmes de manipulation d'arbres et de fichiers (Thèse d'État, 1979)

Volume VII, Chapter 3: Introduction to be written by Maurice Nivat

[1] Complexité des problèmes de décision relatifs aux algorithmes de tri

[2] Decision Problems for Multihead Finite Automata

[5] Generalized Immune Sets

[6] On sets having only hard subsets

[7] Une généralisation de la notion d'ensemble immune

[8] Complexity of classes of languages and operators

[11] Classes de complexité et problèmes complets

[12] Hiérarchies de complexité et réductions entre problèmes [has checked]

[9(10)] Linguistique formelle et linguistique historique

Volume VII, Chapter 4

[B01] L'algorithmique au lycée [read by Christian Paroissin]

Problèmes d'agrégation

Textes sur le PRC MathInfo.

[P05], Mathématiques et informatique [has been checked]

Volume VII, Chapter 5

part 5a:

Introduction to various seminars or meetings

[102] 6-page introduction (gives nice description of the Algo Seminars, to readers who are unfamiliar)

[108a] Introduction: AofA Dagstuhl Seminar Report 68

[108c] Problem 7: AofA Dagstuhl Seminar Report 68

[128] AofA Dagstuhl Seminar Report 119

[(138)139] Introduction to Special issue on Average-Case Analysis of Algorithms

[169] Introduction to Mathematics and Computer Science II

[178] Introduction to Mathematics and Computer Science III

part 5b:

Introductions to books, and related works

[F01] Introduction to: Theory of formal languages with applications

[F02] Introduction to: Average case analysis of algorithms on sequences

part 5c:

[133] Review of Micha Hofri's book

[190] The scientific works of Rainer Kemp (1949--2004)

[A01] American Mathematical Monthly problem E3415

part 5d:

[44a] Definitions for Algorithmique from Encyclopaedia Universalis

[44b] Definitions for Calcul, mathématique from Encyclopaedia Universalis

[98] La calculabilité et ses limites

[162] DEK = 100_8

[note that 44a, 44b, 98 have been proofread,

but 162 has not yet been proofread;

also note: 44a, Section 6, on Algorithmes génétiques, added 14 years later, by Philippe Collard, is not included]

Obituary:

The short obituary written by Bruno Salvy, Bob Sedgewick, Michèle Soria, Wojciech Szpankowski and Brigitte Vallée

*************************************************************************************************************

Note: ALGO seminars to be distributed within the volumes once we have an agreement from the chapter-introduction writers:

s1 B. Salvy

s2 B. Salvy

s3 C. Martínez or H.K. Hwang

s4 B. Vallée

s5 X. Viennot

s6 B. Sedgewick or A. Odlyzko

s7 C. Martínez

s8 W. Szpankowski

s9 B. Vallée

s10 C. Nicaud and F. Bassino

s11 M. Noy and G. Schaeffer

s12 D. Panario

s13 X. Viennot

s14 J.-M. Steyaert

s15 B. Vallée

s16 B. Vallée

s17 M. Drmota

s18 W. Szpankowski

s19 W. Szpankowski

s20 P. Duchon and M. Soria