Previous News
Next News
Issue last updated June 15, 2000.
(from Wojtek's version with title
page added)
As the programme shows, the discussion will focus largely on properties of random discrete structures with emphasis on the following ones.
Strings and patterns.
Trees, of the combinatorial type, of the search type, or of one of the digital ``trie'' varieties.
Graphs, maps (i.e., planar graphs together with an embedding), and geometric configurations.
Allocations, assignments, parking sequences, urn models, and hashing tables.
Permutations and sorts.
Number-theoretic structures like integer compositions, continued fraction representations, or polynomials over finite fields.
Such properties are intimately related to the performances of fundamental algorithms and data structures. Permutations underlie sorting and comparison-based searching. Stringology is at the basis of string searching and other text-based applications. The study of number-theoretic structures paves the way for a better understanding of complexity issues in semi-numerical problems (as Knuth calls them), with ramifications in computer algebra and the basic layers of cryptographic systems. Allocations and graphs are highly relevant to the analysis of combinatorial optimization problems, where the P versus NP question may be declined in a number of ways when it is examined under the probabilistic angle.
The meeting should confirm general trends from earlier years. The emphasis is nowadays not only on average-case analysis in the strict sense, but more and more on the probability distribution of cost-determining parameters. The cross-fertilization between purely analytic methods and stochastic approaches should continue to develop. Indeed, the probabilistic-stochastic approaches provide valuable intuitions together with useful first-order asymptotic models, while analytic methods, whenever applicable, have the potential of producing very precise exact and asymptotic informations on structures and algorithms.
AVERAGE CASE ANALYSIS OF ALGORITHMS ON STRINGS
by WOJTEK SZPANKOWSKI
The book is due to appear some time in the late Fall of the year 2000. (The book is in its final phase of labour) You can find at Szpankowski's site preliminary versions of chapters that should give a flavour of the topics. Roughly, the goal is to provide the reader with a wide range of techniques for analysing probabilistic properties of strings and their companion algorithms. The emphasis is largely on analytic methods including: Complex Asymptotic Methods, Mellin Transform and Its Applications, Analytic Poissonization and Depoissonization. The book also contains a multi-facetted introduction to relevant probabilistic techniques, like: First and Second Moment Methods, Subadditive Ergodic Theorem and Large Deviations, Elements of Information Theory. Also, the necessary combinatorial background is developped in two chapters: Inclusion-Exclusion Principle and Its Variations, Generating Functions.
Amongst the algorithms discussed, we find the Lempel-Ziv data compression algorithms (LZ77 and LZ78), the string editing problem, many variations of the digital trie (Patricia tee, digital search tree, suffix tree), Knuth-Morris-Pratt pattern-matching, source coding and lossy compression (in relation to Shannon theory), variance analyses of data structures, a leader election in distributed computing, and more! Globally, these 500 pages should guide you all the way to contemporary research in the field. (I note that most of the references are to papers that have appeared in the course of the last 15 years and about a quarter are from the 1990's, while the original literature on information theory and probabilistic methods is also there.)
This book is a classic. What you'll find under Wilf's page is a pointer to the latest edition, that of 1994. This text is a nicely written crisp introduction to generatingfunctionologly. I think it is the best text for anyone who seeks a first gentle approach to the subject at either undergraduate or graduate level.
The book starts with basics of couting and recurrences (Chapter 1), continuing with formal power series and generating functions (Chapter 2). Then, Chapter 3 develops general principles of enumeration by generating functions, this much along the lines of Bender and Goldman's theory of ``prefabs'' in the early 1970's. Examples include partitions and the money changing problem, trees of various sorts, and graphs. Chapter 4 deals with various applications of generating functions to permutations, polyominos, as well as to unimodality and congruences of combinatorial sequences. Chapter 5 presents asymptotic methods based on analytic properties of generating functions: from poles to algebraic singlarities (based on Darboux & Pólya) and finally to admissibility of entire functions.
It is rather nice on the part of the publisher (Academic Press/Harcourt Brace) that he allowed this web posting, as I understand the book to be still in print.
On Wilf's page, you can also gain access to a free version of the book A = B by Marko Petkovsek, Herbert Wilf and Doron Zeilberger. I hope to report on this in a future bulletin.
ALGORITHMS SEMINAR 1998-1999,
edited by B
Return to Research News Index