Average case analysis of algorithms on sequences [[electronic resource] /] / Wojciech Szpankowski

• Record Nr.: UNISA996218074803316
• Autore: Szpankowski Wojciech <1952->
• Pubbl/distr/stampa: New York, : John Wiley, c2001
• ISBN: 1-283-30620-4; 9786613306203; 1-118-03277-2; 1-118-03102-4
• Descrizione fisica: 1 online resource (580 p.)
• Collana: Wiley-Interscience series in discrete mathematics and optimization
• Disciplina: 515.24
• Soggetti: Computer algorithms; Algorithms
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Average 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; 2.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; 4.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; 6 Elements of Information Theory6.1 Entropy, Relative Entropy, and Mutual Information; 6.2 Entropy Rate and Rényi's Entropy Rates; 6.2.1 The Shannon-McMillan-Breiman Theorem; 6.2.2 Ré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; 6.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; 7.4 Probability Generating Functions
• Sommario/riassunto: 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-ex

Research-based methods of reading instruction, grades K-3 / / Sharon Vaughn and Sylvia Linan-Thompson

• Record Nr.: UNINA9910966553803321
• Autore: Vaughn Sharon <1952->
• Pubbl/distr/stampa: Alexandria, VA, : Association for Supervision and Curriculum Development, 2004
• ISBN: 9786610933037; 9781416615880; 1416615881; 9781416600688; 141660068X; 9781280933035; 1280933038; 9781416602217; 1416602216
• Edizione: [1st ed.]
• Descrizione fisica: 1 online resource (viii, 151 pages) : illustrations
• Altri autori (Persone): Linan-ThompsonSylvia <1959->
• Disciplina: 372.41
• Soggetti: Reading (Primary) - United States; English language - Study and teaching (Primary) - United States
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Why science matters -- Phonemic awareness -- Phonics and word study -- Fluency -- Vocabulary -- Comprehension -- Putting it all together.
• Sommario/riassunto: What does research tell us about how teachers can most effectively help young students learn to read? In Research-Based Methods of Reading Instruction, Grades K-3, Sharon Vaughn and Sylvia Linan-Thompson explore the research on reading, providing a comprehensive overview of the five core instructional areas and how each affects student achievement: Phonemic awareness Phonics and Word Study Fluency Vocabulary Comprehension The authors include dozens of reading activities and lesson plans that teachers can use immediately, all of which have worked in actual classrooms and are grounded in solid research. A glossary and annotated resource lists will help you better ; understand key reading concepts and find reliable resources, including relevant Web sites. Whether your students have special needs or show no apparent learning difficulties, this book will expand your repertoire of teaching strategies and help you put students on the road to literacy. Sharon Vaughn is the director and H.E. Hartfelder/Southland Corporation regent's chair of the University of Texas Center for Reading and Language Arts in Austin. Sylvia Linan-Thompson is an assistant professor in special education at the University of Texas at Austin.