(2014-09-20) Stable Marriages. Gale-Shapley Algorithm (1962).
No unmarried couple should prefer each other to their respective spouses.
Theoretical Considerations :
Donald Knuth (1938-) showed that the number of stable matchings
may grow exponentially with the size of the dating pool.
He attributed to John Conway (1937-2020) the remark that
the set of stable matchings forms a
distributive lattice.
(2017-04-13) Sorting strings in alphabetical order the human way...
Manually, people don't use pairwise comparisons to sort strings.
To put a messed-up sequence of libray cards in alphabetical order, most people won't resort to
pairwise comparisons at the ouset. Instead, they'll make 26 sets of cards sharing the same first letter
and then sort each of those sets (using the same method recursively) according to the rest of the word.
(Think of what you would do if faced with such a situation.)
The N+1st stage requires a total time proportional to the number of cards which coincide with
at least one other card in the first N letters.
(2017-03-29) String-Matching in Sublinear Time
The longer the pattern, the faster the search.
This is a result from a thesis I submitted at
Polytechnique (1979).
I had effectively rediscovered the Knuth-Morris-Pratt algorithm (published in 1977)
as was soon pointed out to me by
Philippe Flajolet (1948-2011).
