Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Chapter 9: Words and maps covers global properties of words (N-letter strings from an M-letter alphabet), which are well-studied in classical combinatorics (because they model sequences of independent Bernoulli trials) and in classical applied algorithmics (because they model input sequences for hashing algorithms). The chapter also covers random maps (N-letter words from an N-letter alphabet) and discusses relationships with trees and permutations. | ANALYTIC COMBINATORICS PART ONE http aofa.cs.princeton.edu 9. Words and Mappings Orientation Second half of class Surveys fundamental combinatorial classes. Considers techniques from analytic combinatorics to study them . Includes applications to the analysis of algorithms. AN INTRODUCTION TO THE Analysis Algorithms SECOND EDITION ROBERT SED GEWICK PHILIPPE FLAJOLET chapter combinatorial classes type of class type of GF 6 Trees unlabeled OGFs 7 Permutations labeled EGFs 8 Strings and Tries unlabeled OGFs 9 Words and Mappings labeled EGFs Note Many more examples in book than in lectures. 2 ANALYTIC COMBINATORICS PART ONE http aofa.cs.princeton.edu 9. Words and Mappings Words Birthday problem Coupon collector problem Hash tables Mappings .
