discrete mathematics - complete syllabus
discrete mathematics · topics
Propositional logic · induction · stable matching · graph theory · planar graphs · hypercubes · modular arithmetic · polynomials · error correcting codes · counting · infinity · computability · probability - 14 structured notes.
Part I · Logic, Graphs & Number Theory - Notes 1-7
01 · reasoning & proof
Propositional Logic
truth tables, connectives, implication, quantifiers, proof strategies - the language of mathematical reasoning.
↗ mathuser.com/propositional-logic/
∧∨
02 · proof technique
Induction
simple & strong induction, sum formulas, inequalities, binary representation, strengthening the hypothesis.
↗ mathuser.com/induction/
∑
03 · algorithms & design
Stable Matching
Gale-Shapley algorithm, perfect matching, stability, optimality, resident-hospital / college admissions.
↗ mathuser.com/stable-matching/
GS
04 · fundamentals
Graph Theory
vertices, edges, degrees, handshaking lemma, paths, cycles, connectivity, trees - the language of networks.
↗ mathuser.com/graph-theory/
G
05 · drawing & coloring
Planar Graph & Coloring
Euler's formula V−E+F=2, K₅ and K₃,₃ are non-planar, 5-color theorem, four-color theorem.
↗ mathuser.com/planar-graph-and-coloring/
⏢
06 · special families
Hypercubes & Complete
Kₙ : n(n−1)/2 edges, densest. Qₙ : bit-string cubes, recursive construction, large-cut theorem.
↗ mathuser.com/hypercubes-and-complete-graphs/
Qₙ
07 · number theory
Modular Arithmetic & GCD
congruences, inverses, gcd condition, Euclid's algorithm, fast halving proof, last-digit tricks.
↗ mathuser.com/modular-arithmetic-and-gcd/
mod
Part II · Polynomials, Counting & Probability - Notes 8-14
08 · algebra over finite fields
Polynomials
roots, unique interpolation, Lagrange construction, polynomial division, finite fields GF(p), secret sharing scheme.
↗ mathuser.com/polynomials-in-discrete-maths-chapter-8/
p(x)
09 · reliable communication
Error Correcting Codes
erasure vs. general errors, Reed-Solomon encoding, Berlekamp-Welch algorithm, Hamming distance, minimum distance theorem.
↗ mathuser.com/error-correcting-code/
ECC
10 · combinatorics
Counting
product rule, binomial coefficients, stars and bars, Binomial Theorem, inclusion-exclusion, derangements.
↗ mathuser.com/counting-in-discrete-maths/
(ⁿₖ)
11 · set theory
Infinity & Countability
bijections, countable sets, ℤ and ℚ are countable, Cantor's diagonalization, power sets, orders of infinity.
↗ mathuser.com/infinity-and-beyond-discrete-maths/
ℵ₀
12 · theory of computation
Computability
Liar's paradox, quines, Halting Problem proof, reductions, Easy Halting, Gödel's Incompleteness Theorem.
↗ mathuser.com/self-reference-and-computability/
∄
13 · probability theory
Discrete Probability
sample spaces, uniform probability, coin tosses, dice, poker hands, balls and bins, Birthday Paradox, Monty Hall.
↗ mathuser.com/introduction-to-discrete-probability/
P[·]
14 · inference & independence
Conditional Probability
P[A|B], Bayesian inference, Bayes' Rule, Total Probability Rule, mutual independence, Product Rule, Union Bound.
↗ mathuser.com/conditional-probability-independence-and-combinations/
P[A|B]