Knuth also says that "Algorithm R is due to Alan G. Waterman", on TAOCP vol 2 page 144, just below "Algorithm R (Reservoir sampling)". This blog post seems to be a good history of the algorithm: https://markkm.com/blog/reservoir-sampling/ (it was given by Waterman in a letter to Knuth, as an improvement of Knuth's earlier "reservoir sampling" from the first edition).
> All in all, Algorithm R was known to Knuth and Waterman by 1975, and to a wider audience by 1981, when the second edition of The Art of Computer Programming volume 2 was published.
> All in all, Algorithm R was known to Knuth and Waterman by 1975, and to a wider audience by 1981, when the second edition of The Art of Computer Programming volume 2 was published.