How to do CS Theory
35:51Street Fighting Mathematics
26:10Big O and friends
28:10Harmonic Numbers Asymptotics
22:18Asymptotics Tricks
25:00The Central Binomial Coefficient
1:00:26Birthday Paradox Asymptotics
18:09Factorial Asymptotics, Stirling's Formula
28:26Binomial Coefficients Asymptotics
35:57Central Limit Theorem
24:22Gaussian Random Variables
38:31Berry–Esseen Theorem
16:07Markov and Chebyshev Inequalities
38:22Proof of the Chernoff Bound
24:34Chernoff, Hoeffding, etc. bounds
17:47Computational Models: Turing Machines
25:31Computational Models: Circuits
29:07The Word RAM Model
25:30Birthday Paradox Asymptotics
This lecture analyzes the asymptotic behavior of the Birthday Paradox, determining the number of items needed to achieve a 1/2 probability of collision when distributed into a fixed number of bins. It references foundational texts in combinatorics and asymptotic analysis.
Asymptotics of the Birthday Paradox -- how many balls do you need to throw into m bins before there's ~1/2 chance of a collision? Lecture 3a of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
The Central Binomial Coefficient
Next · Lecture 8Factorial Asymptotics, Stirling's Formula