Probabilistic Analysis of Algorithms

1 Introduction.- 1.1 Criteria for the Performance and Quality of Algorithms.- 1.2 The Analysis of a Very Simple Algorithm.- 1.3 Comments on Sources and Resources.- Exercises and Complements.- 2 Tools of the Trade.- 2.1 Introduction to Asymptotics.- 2.1.1 Asymptotic Notation.- 2.1.2 Summation Asymptotics.- 2.1.3 Euler's Summation Formula.- Exercises and Complements.- 2.2 Generating Functions.- 2.2.1 Elementary Properties and Applications.- 2.2.2 Probability gf's (pgf), Moment gf's.- 2.2.3 Lagrange Expansion and Applications.- 2.2.4 The Poisson Transform.- Exercises and Complements.- 2.3 Integral Transforms (it's).- 2.3.1 Laplace Transform.- 2.3.2 Mellin Transform.- 2.3.3 Mellin Summation Formula.- Exercises and Complements.- 2.4 Combinatorial Calculus (The Symbolic Operator Method).- 2.4.1 Elementary Examples.- 2.4.2 Admissible Combinatorial Constructions.- 2.4.3 Operator Methods.- Exercises and Complements.- 2.5 Asymptotics from Generating Functions.- 2.5.1 Complex Functions - Definitions and Theorems.- 2.5.2 Expansions at Singularities.- 2.5.3 Entire Functions.- Exercises and Complements.- 2.6 Selected Results from Probability Theory.- 2.6.1 The Representation of an Algorithm by a Markov Chain.- 2.6.2 Inequalities for Sums of Bounded Random Variables.- 2.6.3 Wald's Identity.- Exercises and Complements.- 3 Algorithms over Permutations.- 3.1 MAX - Locating the Largest Term in a Permutation.- Exercises and Complements.- 3.2 Representations of Permutations.- 3.2.1 Cycles in a Permutation.- 3.2.2 Inversions.- Exercises and Complements.- 3.3 Analysis of Sorting Algorithms.- 3.3.1 Insertion Sort.- 3.3.2 Shell Sort.- 3.3.3 Linear Probing Sort.- Exercises and Complements.- 4 Algorithms for Communications Networks.- 4.1 The Efficiency of Multiple Connections.- 4.1.1 Disjointly Shared Channels - Capacity Considerations.- 4.1.2 Counting Realizable Configurations.- 4.1.3 Asymptotic Capacity Estimates.- Exercises and Complements.- 4.2 Collision Resolution Stack Algorithms.- 4.2.1 Channel Capacity Analysis.- 4.2.2 Top of Stack Probabilities and Message Delay.- 4.2.3 Message Delay via Renewal Considerations.- 4.2.4 Note on Computations.- Exercises and Complements.- 5 Bin Packing Heuristics.- 5.1 The Next-Fit Bin Packing Algorithm.- 5.1.1 Regularity and Convergence Properties.- 5.1.2 Next-Fit with X ~ U (0,1) - Expected Values.- 5.1.3 Next-Fit with X~ U(0,a) - Expected Values.- 5.1.4 The Distribution of An(NF), when X~ U(0,1).- Exercises and Complements.- 5.2 The Next-Fit-Decreasing Bin Packing Algorithm.- 5.2.1 Direct Evaluation of Bin Requirements.- 5.2.2 Asymptotic Bounds on Moments.- Exercises and Complements.- Appendix A: Binomial Coefficients.- Appendix B: Stirling Numbers.- Appendix C: Inequalities.- References.- Notation Index.