Combinatorics, Inclusion/Exclusion
1Today we talked more about combinatorics, including ways of estimating about how long before we run out of social security numbers or license plates, how quickly a password can be guessed, and so forth. It's an essential math skill for a computer scientist to use when making ballpark figures for run times. It's nice to know if a program will run in a couple minutes, a couple days, or the heat death of the universe.
We then moved on to the Inclusion/Exclusion Principle, which governs the size of a set when doing Union operations. For Unioning two sets together, you take the size of each set, add them together, then delete the count of all duplicates (given by the intersection). For bigger combinations of sets, you figure out the size by adding the size of all the sets by themselves, subtracting the intersection of all pairs of sets, adding in the intersection of all triads of sets, subtracting out all the different ways of putting four sets together, and so forth.
We finished off by talking about how to do input in C++ using getline and stringstream, which is a really useful and powerful tool for parsing input. Don't leave home without it.
Other Videos By Bill Kerney
| 2021-09-15 | Truth Tables II + Denying the Antecedent + Affirming the Consequent |
| 2021-09-14 | Under the Hood I + Lighting + Special Effects in UE4 |
| 2021-09-14 | Introducing Readlib |
| 2021-09-14 | C++ I/O and Digital Logic |
| 2021-09-13 | Function Overloading and Commenting Code |
| 2021-09-13 | Truth Tables - AND, OR, NOT |
| 2021-09-11 | Call by Reference |
| 2021-09-10 | Modus Ponens and Modus Tollens |
| 2021-09-10 | SVN, Voronoi |
| 2021-09-10 | GDC Talks, Landscape III, Material Functions |
| 2021-09-10 | Combinatorics, Inclusion/Exclusion |
| 2021-09-08 | Functions Part II |
| 2021-09-08 | Arguments + Invalid/Valid/Sound |
| 2021-09-07 | Voroni |
| 2021-09-07 | CSG, Sprinting, Water (Old and New) |
| 2021-09-07 | Constexpr, Permutations, Combinations, Binomial Theorem, and Infinite Sets |
| 2021-09-03 | Functions in C++ Part I |
| 2021-09-03 | Five Theories of Truth |
| 2021-09-02 | UE4 Blueprints |
| 2021-09-02 | Set Theory I |
| 2021-09-02 | The Laser Zombies |