9780471240631

Average Case Analysis of Algorithms on Sequences

by
  • ISBN13:

    9780471240631

  • ISBN10:

    047124063X

  • Format: Hardcover
  • Copyright: 2001-04-16
  • Publisher: Wiley-Interscience
  • Purchase Benefits
  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $211.00 Save up to $8.44
  • Buy New
    $202.56
    Add to Cart Free Shipping

    PRINT ON DEMAND: 2-4 WEEKS. THIS ITEM CANNOT BE CANCELLED OR RETURNED.

Supplemental Materials

What is included with this book?

  • The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

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

Rewards Program

Write a Review