Average Case Analysis of Algorithms on Sequences

by Szpankowski, Wojciech

• ISBN13: 9780471240631
• ISBN10: 047124063X
• Edition: 1st
• Format: Hardcover
• Copyright: 2001-04-16
• Publisher: Wiley-Interscience

Summary

A timely book on a topic that has witnessed a surge of interest over the last decade, owing in part to several novel applications, most notably in data compression and computational molecular biology. It describes methods employed in average case analysis of algorithms, combining both analytical and probabilistic tools in a single volume. * Tools are illustrated through problems on words with applications to molecular biology, data compression, security, and pattern matching. * Includes chapters on algorithms and data structures on words, probabilistic and analytical models, inclusion-exclusion principles, first and second moment methods, subadditive ergodic theorem and large deviations, elements of information theory, generating functions, complex asymptotic methods, Mellin transform and its applications, and analytic poissonization and depoissonization. * Written by an established researcher with a strong international reputation in the field.

Author Biography

WOJCIECH SZPANKOWSKI, PhD, is Professor of Computer Science at Purdue University and has held visiting research positions at the Technical University of Gdansk, McGill University, INRIA, the Technical University of Vienna, University of Witwatersrand, Hewlett-Packard Laboratories, and Stanford University. He is the author of over 100 scientific publications in the areas of analysis of algorithms, information theory, performance evaluation of computer networks, stability of distributed systems, and queueing theory.

Table of Contents

Forword	xiii
Preface	xv
Acknowledgments	xxi
PART I PROBLEMS ON WORDS
Data Structures and Algorithms on Words	3	(22)
Digital Trees	4	(5)
Data Compression: Lempel-Ziv Algorithms	9	(6)
Lempel-Ziv'77 Algorithm	10	(1)
Lempel-Ziv'78 Algorithm	11	(1)
Extensions of Lempel-Ziv Schemes	12	(3)
Pattern Matching	15	(2)
Shortest Common Superstring	17	(3)
String Editing Problem	20	(2)
Optimization Problems	22	(1)
Exercises	23	(2)
Probabilistic and Analytical Models	25	(26)
Probabilistic Models of Strings	26	(4)
Review of Probability	30	(5)
Some Useful Inequalities	30	(2)
Types of Stochastic Convergence	32	(3)
Review of Complex Analysis	35	(4)
Special Functions	39	(7)
Euler's Gamma Function	40	(4)
Riemann's Zeta Function	44	(2)
Extensions and Exercises	46	(5)
PART II PROBABILISTIC AND COMBINATORIAL TECHNIQUES
Inclusion-Exclusion Principle	51	(22)
Probabilistic Inclusion-Exclusion Principle	52	(4)
Combinatorial Inclusion-Exclusion Principle	56	(3)
Applications	59	(10)
Depth in a Trie	60	(1)
Order Statistics	61	(3)
Longest Aligned Word	64	(5)
Extensions and Exercises	69	(4)
The First and Second Moment Methods	73	(33)
The Methods	74	(6)
Applications	80	(23)
Markov Approximation of a Stationary Distribution	80	(2)
Excursion into Number Theory	82	(2)
Height in Tries	84	(10)
Height in PATRICIA Tries	94	(3)
Height in Digital Search Trees	97	(2)
Height in a Suffix Tree	99	(4)
Extensions and Exercises	103	(3)
Subadditive Ergodic Theorem and Large Deviations	106	(43)
Subadditive Sequence	107	(6)
Subadditive Ergodic Theorem	113	(3)
Martingales and Azuma's Inequality	116	(9)
Large Deviations	125	(9)
Applications	134	(10)
Edit Distance	134	(2)
Knuth-Morris-Pratt Pattern Matching Algorithms	136	(5)
Large Deviations of a Random Sequence	141	(3)
Extensions and Exercises	144	(5)
Elements of Information Theory	149	(64)
Entropy, Relative Entropy, and Mutual Information	151	(3)
Entropy Rate and Renyi's Entropy Rates	154	(5)
The Shannon-McMillan-Breiman Theorem	154	(3)
Renyi's Entropy Rates	157	(2)
Asymptotic Equipartition Property	159	(13)
Typical Sequences	159	(2)
Jointly Typical Sequences	161	(2)
AEP for Biased Distributions	163	(2)
Lossy Generalizations of AEP	165	(7)
Three Theorems of Shannon	172	(15)
Source Coding Theorem	172	(4)
Channel Coding Theorem	176	(5)
Rate Distortion Theorem	181	(6)
Applications	187	(17)
Phrase Length in the Lempel-Ziv Scheme and Depth in a Suffix Tree	187	(8)
Shortest Common Superstring Problem	195	(5)
Fixed-Database Lossy Lempel-Ziv Algorithm	200	(4)
Extensions and Exercises	204	(9)
PART III ANALYTIC TECHNIQUES
Generating Functions	213	(65)
Ordinary Generating Functions	215	(14)
Formal Power Series	215	(3)
Combinatorial Calculus	218	(4)
Elements of Analytic Theory	222	(5)
Generating Functions Over an Arithmetic Progression	227	(2)
Exponential Generating Functions	229	(6)
Elementary Properties	229	(2)
Labeled Combinatorial Structures	231	(4)
Cauchy, Lagrange and Borel Formulas	235	(8)
Cauchy Coefficient Formula	235	(1)
Lagrange Inversion Formula	236	(6)
Borel Transform	242	(1)
Probability Generating Functions	243	(3)
Dirichlet Series	246	(10)
Basic Properties	247	(2)
Euler Products	249	(2)
Perron-Mellin Formula	251	(5)
Applications	256	(19)
Recurrences Arising in the Analysis of Digital Trees	256	(6)
Pattern Occurrences in a Random Text	262	(10)
Delange's Formula for a Digital Sum	272	(3)
Extensions and Exercises	275	(3)
Complex Asymptotic Methods	278	(120)
Introduction to Asymptotic Expansions	281	(9)
Definitions and Notations	281	(3)
From Taylor Expansion to Asymptotic Series	284	(6)
Basic Methods	290	(22)
Euler-Maclaurin Summation Formula	290	(6)
Matched Asymptotics and the WKB Method	296	(8)
Uniform Distribution of Sequences	304	(8)
Small Singularities of Analytic Functions	312	(19)
Polar Singularities	314	(4)
Algebraic Singularities: Singularity Analysis	318	(13)
Large Singularities: Saddle Point Method	331	(22)
Laplace Method	332	(5)
Method of Steepest Descent	337	(13)
Local Central Limit Theorem and Large Deviations Revisited	350	(3)
Finite Sums as Complex Integrals	353	(9)
Limiting Distributions	362	(10)
Discrete Limit Laws Through PGF	362	(3)
Continuous Limit Laws by Integral Transforms	365	(7)
Applications	372	(16)
Variations on Approximate Self-Overlapping Words	372	(4)
Redundancy Rate for Memoryless Sources	376	(5)
Limiting Distribution of the Depth in Digital Search Trees	381	(7)
Extensions and Exercises	388	(10)
Mellin Transform and Its Applications	398	(44)
Basic Properties	400	(7)
Asymptotic Properties of the Mellin Transform	407	(10)
Extension to the Complex Plane	417	(4)
Applications	421	(14)
Variance of the Depth in a Generalized Digital Search Tree	421	(4)
Redundancy of Renewal Processes	425	(10)
Extensions and Exercises	435	(7)
Analytic Poissonization and Depoissonization	442	(78)
Analytic Poissonization and the Poisson Transform	446	(7)
Poisson Transform	446	(3)
Asymptotic Poissonization	449	(4)
Basic Depoissonization	453	(13)
Algebraic Depoissonization	454	(1)
Asymptotic Depoissonization	455	(11)
Generalizations of Depoissonization	466	(14)
A Full Asymptotic Depoissonization	466	(6)
Exponential Depoissonization	472	(3)
General Depoissonization Tool	475	(5)
Moments and Limiting Distributions	480	(5)
Moments	481	(1)
Limiting Distributions	482	(3)
Applications	485	(27)
Leader Election Algorithm	486	(5)
Depth in a b-Digital Search Tree for the Biased Memoryless Model	491	(10)
Depth in a Digital Search Tree with a Markovian Source	501	(11)
Extensions and Exercises	512	(8)
Bibliography	520	(23)
Index	543