Degrees

Discrete mathematics

Logic, proof, sets, counting, recurrences, graphs and number theory: the mathematics that every algorithm, database and cipher is built on.

Course · 8 lessons · 60 min

Taught inComputer ScienceData ScienceArtificial Intelligence

  1. 1Propositional logic and truth tablesFreePropositions, connectives, truth tables and equivalences: the algebra behind every if statement, search filter and logic gate.1854–1938 · 7 min
  2. 2Predicates and quantifiersPropositional logic cannot say “every” or “some”. Predicates and quantifiers can, and they are the logic inside every SQL query.1879 · 7 min
  3. 3Proof techniques: direct, contradiction and inductionHow to show a statement holds for every case, not just the ones you tried: direct proof, contrapositive, contradiction and induction.c. 300 BC–today · 8 min
  4. 4Sets, relations and functionsThe vocabulary of all of computing: sets and their operations, relations and their properties, and functions that are injective, surjective or bijective.1874–1970 · 7 min
  5. 5Combinatorics: counting without listingProduct rule, permutations, combinations, inclusion–exclusion and the pigeonhole principle: how to count what you could never enumerate.17th century–today · 7 min
  6. 6Recurrences and how to solve themDefining a sequence by its earlier terms, and turning that definition into a closed form: unrolling, characteristic equations and divide and conquer.1202–today · 8 min
  7. 7Graphs: degrees, paths, trees, Euler and HamiltonVertices and edges model networks, maps, dependencies and social links. Degrees, paths, trees, and the two famous tours: Euler's and Hamilton's.1730s–today · 8 min
  8. 8Number theory for computingDivisibility, the gcd and Euclid's algorithm, modular arithmetic and number bases: the arithmetic behind hashing, checksums and public-key cryptography.c. 300 BC–1978 · 8 min