Hash tables & probability, part 2

Discussion of expected value of a random variable & linearity of expectation. The "balls and bins" model for hash tables, and introduction to special cases (coupon collector, birthday problem, binomial & poisson r.v.s, etc) that we can model with random variables. These materials are also openly available on figshare. Please cite this work; this ensures that funding agencies see the impact and importance of these open learning materials. Langmead, Ben (2024). Sketching & randomized data structures: learning materials. figshare. Collection. https://doi.org/10.6084/m9.figshare.c.7253734.v1 ── Course & channel links ── Course playlist: Sketching and Randomized Data Structures https://www.youtube.com/playlist?list=PL2mpR0RYFQsAR5RyB54FyEE9vUiGtCSZM ── About the author ── Ben Langmead is a Professor of Computer Science at Johns Hopkins University, where his research spans bioinformatics, computational biology, and data-intensive science. He is the author of Bowtie and Bowtie 2; his group has also developed software like Kraken 2 and resources like recount3 and Index Zone, as well as methods for pangenome indexing and querying, based on e.g. the r-index and move structure. His group's methods have been cited over 130,000 times, and he is the winner of awards including an NSF CAREER award, a Sloan Research Fellowship, the Benjamin Franklin award for contributions to open access, and multiple awards for teaching and mentorship. Ben is the founder and principal of InOrder Labs LLC (https://inorderlabs.com), an expert consulting firm in bioinformatics and computational biology. Channel: https://www.youtube.com/@BenLangmead Teaching materials: https://langmead-lab.org/teaching.html