9. Words and Maps
This chapter 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.
9.1 Hashing with Separate Chaining
9.2 Basic Properties of Words
9.3 Birthday Paradox and Coupon Collector Problem
9.4 Occupancy Restrictions and Extremal Parameters
9.5 Occupancy Distributions
9.6 Open Addressing Hashing
9.7 Maps
9.8 Integer Factorization and Maps
Selected Exercises
9.5
For $M=365$, how many people are needed to be 99% sure that two have the same birthday?9.22
Give a plot (for $M=365$) of the probability that three people have the same birthday.9.23
For $M=365$, how many people are needed to be 50% sure that three have the same birthday? Four?9.28
What is the probability that one urn will get all the balls when 100 balls are randomly distributed among 100 urns?9.29
What is the probability that each urn will get one ball when 100 balls are randomly distributed among 100 urns?9.37
Find $[z^n]e^{\alpha C(z)}$ where $C(z)$ is the Cayley function (see the discussion at the end of Section 6.14 and in Section 9.7 in this chapter).59.38
(``Abel's binomial theorem.'') Use the result of the previous exercise and the identity $e^{(\alpha+\beta)C(z)}=e^{\alpha C(z)}e^{\beta C(z)}$ to prove that $$(\alpha+\beta)(n+\alpha+\beta)^{n-1} =\alpha\beta\sum_k{n\choose k}(k+\alpha)^{k-1}(n-k+\beta)^{n-k-1}.$$9.53
A mapping with no repeated integers is a permutation. Give an efficient algorithm for determining whether a mapping is a tree.9.58
Describe the graph structure of partial mappings, where the image of a point may be undefined. Set up the corresponding EGF equations and check that the number of partial mappings of size $N$ is $(N+1)^N$.9.60
Generate 100 random maps of size 100, 1000, and 10000 and empirically verify that about 48% of the nodes are in the largest tree, that about 76% of the nodes are in the largest cycle, and that, in a random map of size $N$, the number of nodes in the longest tail, cycle, and rho-path are about $1.74\sqrt{N}$, $.78\sqrt{N}$, and $2.41\sqrt{N}$, respectively.9.61
Use Floyd's method to test the random number generator on your machine for short cycles.9.99
Show that the probability that a random mapping of size N has no singleton cycles is $\sim 1/e$, the same as for permutations (!).