Algorithmics of Nonuniformity. Tools and Paradigms

Contents......Page 3
Preface......Page 9
Notation......Page 13
Computing machines & models......Page 16
Asymptotic notation......Page 22
Notes & sources......Page 24
Generating functions......Page 27
Stirling numbers - combinatorial interpretation......Page 38
Expansion of generating functions......Page 43
Generating functions in probability......Page 50
Generating functions in the solution of recurrences......Page 54
Notes & sources......Page 58
Symbolic Calculus......Page 63
Admissible operations......Page 65
Applications of the symbolic calculus......Page 74
Notes & sources......Page 83
Languages & Generating Functions......Page 84
Regular languages......Page 87
FSA......Page 90
FSA & regular languages......Page 93
Generating functions & their regular languages......Page 98
Counting regular languages......Page 101
Notes & sources......Page 115
Probability in Algorithmics......Page 117
Random variables......Page 120
Characteristic functions......Page 130
Mixed distributions......Page 132
Inequalities......Page 134
Modes of probabilistic convergence......Page 143
Some classic results from probability theory......Page 150
Central limit theorems......Page 156
Martingales......Page 159
Generating random numbers......Page 162
Notes & sources......Page 166
Mellin transform......Page 173
Poissonization......Page 183
Notes & sources......Page 194
Classic Pólya urns......Page 198
Tenability......Page 200
Pólya urns with ball activity......Page 201
Nonuniform Pólya process......Page 225
Notes & sources......Page 233
Restricted permutations......Page 237
Automata for restricted permutations......Page 249
Random multisets......Page 254
Binary search trees......Page 269
Digital trees......Page 284
Notes & sources......Page 297
Data comparisons......Page 305
Insertion sort......Page 307
Quick sort......Page 316
Notes & sources......Page 328
Recursive Trees......Page 331
Uniform recursive trees......Page 333
Trees with vertex affinity proportional to age......Page 339
Recursive trees grown under the power of choice......Page 344
Preferential attachment tree model......Page 352
Blocks trees......Page 359
Hoppe trees......Page 370
Notes & sources......Page 375
Series-Parallel Graphs......Page 379
Some models of binary series-parallel graphs......Page 381
Enumerating binary series-parallel graphs......Page 384
Order of binary series-parallel graphs......Page 387
Path length in binary series-parallel graphs......Page 391
Series-parallel graph with unrestricted degrees......Page 401
Notes & sources......Page 409
Biblio......Page 411
Chapter 1......Page 428
Chapter 2......Page 430
Chapter 3......Page 448
Chapter 4......Page 453
Chapter 5......Page 463
Chapter 6......Page 494
Chapter 7......Page 501
Chapter 8......Page 510
Chapter 9......Page 539
Chapter 10......Page 546
Chapter 11......Page 560
Index......Page 568