LEADER 05342nam 2200625Ia 450 001 996218074803316 005 20230607223649.0 010 $a1-283-30620-4 010 $a9786613306203 010 $a1-118-03277-2 010 $a1-118-03102-4 035 $a(CKB)2550000000056719 035 $a(EBL)694802 035 $a(OCoLC)778616739 035 $a(SSID)ssj0000613258 035 $a(PQKBManifestationID)11356282 035 $a(PQKBTitleCode)TC0000613258 035 $a(PQKBWorkID)10584723 035 $a(PQKB)11128645 035 $a(MiAaPQ)EBC694802 035 $a(EXLCZ)992550000000056719 100 $a20000519d2001 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aAverage case analysis of algorithms on sequences$b[electronic resource] /$fWojciech Szpankowski 210 $aNew York $cJohn Wiley$dc2001 215 $a1 online resource (580 p.) 225 1 $aWiley-Interscience series in discrete mathematics and optimization 300 $aDescription based upon print version of record. 311 $a0-471-24063-X 320 $aIncludes bibliographical references and index. 327 $aAverage Case Analysis of Algorithms on Sequences; Contents; Forword; Preface; Acknowledgments; PART I PROBLEMS ON WORDS; 1 Data Structures and Algorithms on Words; 1.1 Digital Trees; 1.2 Data Compression: Lempel-Ziv Algorithms; 1.2.1 Lempel-Ziv'77 Algorithm; 1.2.2 Lempel-Ziv'78 Algorithm; 1.2.3 Extensions of Lempel-Ziv Schemes; 1.3 Pattern Matching; 1.4 Shortest Common Superstring; 1.5 String Editing Problem; 1.6 Optimization Problems; 1.7 Exercises; 2 Probabilistic and Analytical Models; 2.1 Probabilistic Models of Strings; 2.2 Review of Probability; 2.2.1 Some Useful Inequalities 327 $a2.2.2 Types of Stochastic Convergence2.3 Review of Complex Analysis; 2.4 Special Functions; 2.4.1 Euler's Gamma Function; 2.4.2 Riemann's Zeta Function; 2.5 Extensions and Exercises; PART II PROBABILISTIC AND COMBINATORIAL TECHNIQUES; 3 Inclusion-Exclusion Principle; 3.1 Probabilistic Inclusion-Exclusion Principle; 3.2 Combinatorial Inclusion-Exclusion Principle; 3.3 Applications; 3.3.1 Depth in a Trie; 3.3.2 Order Statistics; 3.3.3 Longest Aligned Word; 3.4 Extensions and Exercises; 4 The First and Second Moment Methods; 4.1 The Methods; 4.2 Applications 327 $a4.2.1 Markov Approximation of a Stationary Distribution4.2.2 Excursion into Number Theory; 4.2.3 Height in Tries; 4.2.4 Height in PATRICIA Tries; 4.2.5 Height in Digital Search Trees; 4.2.6 Height in a Suffix Tree; 4.3 Extensions and Exercises; 5 Subadditive Ergodic Theorem and Large Deviations; 5.1 Subadditive Sequence; 5.2 Subadditive Ergodic Theorem; 5.3 Martingales and Azuma's Inequality; 5.4 Large Deviations; 5.5 Applications; 5.5.1 Edit Distance; 5.5.2 Knuth-Morris-Pratt Pattern Matching Algorithms; 5.5.3 Large Deviations of a Random Sequence; 5.6 Extensions and Exercises 327 $a6 Elements of Information Theory6.1 Entropy, Relative Entropy, and Mutual Information; 6.2 Entropy Rate and Re?nyi's Entropy Rates; 6.2.1 The Shannon-McMillan-Breiman Theorem; 6.2.2 Re?nyi's Entropy Rates; 6.3 Asymptotic Equipartition Property; 6.3.1 Typical Sequences; 6.3.2 Jointly Typical Sequences; 6.3.3 AEP for Biased Distributions; 6.3.4 Lossy Generalizations of AEP; 6.4 Three Theorems of Shannon; 6.4.1 Source Coding Theorem; 6.4.2 Channel Coding Theorem; 6.4.3 Rate Distortion Theorem; 6.5 Applications; 6.5.1 Phrase Length in the Lempel-Ziv Scheme and Depth in a Suffix Tree 327 $a6.5.2 Shortest Common Superstring Problem6.5.3 Fixed-Database Lossy Lempel-Ziv Algorithm; 6.6 Extensions and Exercises; PART III ANALYTIC TECHNIQUES; 7 Generating Functions; 7.1 Ordinary Generating Functions; 7.1.1 Formal Power Series; 7.1.2 Combinatorial Calculus; 7.1.3 Elements of Analytic Theory; 7.1.4 Generating Functions Over an Arithmetic Progression; 7.2 Exponential Generating Functions; 7.2.1 Elementary Properties; 7.2.2 Labeled Combinatorial Structures; 7.3 Cauchy, Lagrange and Borel Formulas; 7.3.1 Cauchy Coefficient Formula; 7.3.2 Lagrange Inversion Formula; 7.3.3 Borei Transform 327 $a7.4 Probability Generating Functions 330 $aA 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-ex 410 0$aWiley-Interscience series in discrete mathematics and optimization. 606 $aComputer algorithms 606 $aAlgorithms 615 0$aComputer algorithms. 615 0$aAlgorithms. 676 $a515.24 700 $aSzpankowski$b Wojciech$f1952-$0553750 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996218074803316 996 $aAverage case analysis of algorithms on sequences$9979053 997 $aUNISA