Learning objectives
By the end of this week you can:
- 1 Apply the product rule, the sum rule and the subtraction rule.
- 2 Count arrangements with permutations and selections with combinations.
- 3 Use the pigeonhole principle and its generalized form.
- 4 Estimate password spaces and brute-force times.
- 5 Simulate the birthday paradox and connect it to hash collisions.
★ the wow moment
With 23 people in a room, two probably share a birthday.
It feels impossible, but counting says so, and a 10-line simulation agrees. The same math tells attackers how many tries it takes to find a hash collision, which is why hash sizes are chosen the way they are.
Topics
- Product and sum rules
- Inclusion–exclusion for two sets
- The pigeonhole principle
- Permutations and combinations
- Binomial coefficients and Pascal’s triangle
Before class
- Skim Rosen 6.1–6.3 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Security
Password policies and key lengths are chosen by counting the search space an attacker must cover.
-
Hashing
The pigeonhole principle guarantees collisions; the birthday bound says how soon they appear.
-
Testing
Combinatorial (pairwise) testing picks a small set of configurations that covers every pair of options.
Lab 11: Counting and the Birthday Paradox
Count with itertools, verify formulas, estimate password spaces and simulate the birthday paradox.
due Fri, Dec 18 · 23:59 · 100 points · opens in week 13
Go deeper
- Discrete Mathematics: An Open Introduction (Oscar Levin) · Chapter 1, counting
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapter 15, cardinality rules
- Birthday problem (Wikipedia)
Tags:countingproduct rulepigeonholepermutationcombinationbinomialbirthday paradox