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).5
9.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.
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 (!).
