F06

Discrete Math

“Counting things without counting each one”

SetsFreeA set is a collection where order doesn't matter and nothing appears twice. You'll learn the language of sets (members, subsets, union, intersection, difference), see each operation as a picture, and use Python's sets to answer real questions instantly. · 13 min
FunctionsFreeIn math, a function is a rule that gives every input exactly one output. You'll draw functions as arrows, learn the three kinds that matter most (one-to-one, onto, and bijections), and see why bijections are how mathematicians count and compare sizes. · 14 min
RelationsFreeA relation says which pairs of things are connected, like "is a friend of" or "is less than". You'll learn the three properties that matter most (reflexive, symmetric, transitive), meet equivalence relations that sort things into groups, and order tasks with partial orders. · 14 min
Infinity and countability🔒 MembersSome infinities are bigger than others. Using bijections from lesson 2, you'll see why there are exactly as many even numbers as whole numbers, why fractions can be listed one by one, and why the real numbers can't, using one of the most beautiful arguments in mathematics. · 15 min
Counting: sum and product rules🔒 MembersHow many passwords, outfits or license plates are possible? Two simple rules answer almost every counting question, without listing anything. You'll use them to see why long passwords beat clever ones, and count "at least one" by counting the opposite. · 13 min
Permutations and combinations🔒 MembersDoes order matter? A race podium cares who came first; a team doesn't. You'll count arrangements (permutations) and selections (combinations), learn the "n choose k" formula and why it divides, and work out real lottery and card odds. · 14 min
The pigeonhole principle🔒 MembersIf more pigeons than holes, some hole holds two. This almost-too-simple idea proves surprising facts, like why every hash function has collisions and why no program can compress every file. You'll use it to find collisions and to guarantee how crowded the busiest bucket must be. · 13 min
Inclusion–exclusion🔒 MembersWhen groups overlap, adding their sizes counts some things twice. Inclusion–exclusion fixes that with a simple add-subtract-add pattern. You'll use it on surveys and number puzzles, and see it on the Venn diagram from lesson 1. · 13 min
The binomial theorem🔒 MembersPascal's triangle holds every "n choose k" number, and each one is the sum of the two above it. You'll see why, use it to expand (a + b)ⁿ without multiplying everything out, and prove identities by counting the same thing in two ways. · 14 min
Recurrences🔒 MembersA recurrence defines each term from the ones before it, like Fibonacci or the moves in the Tower of Hanoi. You'll turn recurrences into closed formulas you can compute instantly, and see where the mysterious 1.6ⁿ from tree recursion really comes from. · 15 min
Graphs🔒 MembersA graph is dots joined by lines, and it models friendships, road maps, networks and the web. You'll build graphs by tapping, learn the words (vertices, edges, degree), and discover the handshake lemma, a tiny counting fact with surprising consequences. · 14 min
Paths, connectivity and trees🔒 MembersCan you get from here to there? You'll learn paths and cycles, find the separate pieces of a graph with code, and meet trees, the cheapest way to connect everything, which always use exactly one edge fewer than they have vertices. · 15 min
Euler and Hamilton🔒 MembersCan you trace a drawing without lifting your pen? In 1736, Euler answered with one simple rule about degrees, founding graph theory. You'll use his rule, then meet its innocent-looking cousin, visiting every vertex once, which nobody knows how to solve quickly. · 15 min
Coloring and bipartite graphs🔒 MembersGive every vertex a color so that neighbors never match. That simple rule schedules exams, assigns radio frequencies and allocates computer memory. You'll color graphs by hand and with a greedy algorithm, and learn exactly when two colors are enough. · 15 min
Directed graphs and DAGs🔒 MembersSome connections only go one way. Socks come before shoes, and Python comes before Data Structures. Turn edges into arrows and you can plan any job that has a "this first" rule, as long as the arrows never loop back on themselves. · 15 min
Divisibility and the GCD🔒 MembersWhat's the biggest square tile that covers a floor with no cutting? The answer is the greatest common divisor, and a 2,300-year-old trick finds it in a handful of steps, even for numbers with hundreds of digits. It's the first gear in the machine that keeps the internet's secrets. · 15 min
Modular arithmetic🔒 MembersTen o'clock plus five hours is three o'clock. That's arithmetic that wraps around, and computers do it constantly, from hash tables to check digits to the numbers inside the CPU. You'll walk around a clock, discover which step sizes visit every hour, and validate a real book barcode. · 15 min
Primes and modular inverses🔒 MembersPrimes are the atoms of whole numbers. Every number splits into primes in exactly one way. On a clock, a prime size means something magic: every multiplication (except by 0) can be undone. That "undo" button is the secret key of RSA. · 15 min
Fermat's little theorem and fast powers🔒 MembersWhat's the remainder of 7 to the power 1000, divided by 13? The number itself has 846 digits, yet you can answer in your head. Powers on a clock go round in circles, and a trick called repeated squaring computes giant powers in a few dozen steps. Both are the engine of RSA. · 15 min
Boss level: RSA from scratch🔒 MembersHow can you send your card number to a shop you've never met, over a network anyone can listen to? RSA lets anyone lock a message that only one person can unlock. You'll build your own keys, encrypt and decrypt, then switch sides and crack a message whose key is too small. · 40 min

💼 Already know this course?

Placement tests are coming soon. Until then, you can mark it as known so it’s colored in on your map. You can undo this any time.

Lessons