Unit · year 1

MU-105 · Discrete Mathematics

Threads structure · number24 lectures6 theorems

Counting, graphs, and modular arithmetic — the mathematics of the finite.

PREREQUISITES

L01	Counting Principles: Sum and Product —
L02	Permutations and Combinations —
L03	Binomial Coefficients and Pascal's Triangle The binomial theorem
L04	The Binomial Theorem The binomial theorem
L05	Combinatorial Identities and Double Counting The binomial theorem
L06	The Inclusion–Exclusion Principle The inclusion–exclusion principle
L07	Derangements and Applications The inclusion–exclusion principle
L08	Recurrence Relations —
L09	Generating Functions: First Steps —
L10	Modular Arithmetic and Congruences —
L11	Linear Congruences and Modular Inverses —
L12	Fermat's Little Theorem Fermat's little theorem
L13	The Chinese Remainder Theorem The Chinese remainder theorem
L14	Applications to Cryptography Fermat's little theorem, The Chinese remainder theorem
L15	Graphs: Definitions and Representations —
L16	Degree Sequences and the Handshaking Lemma The handshaking lemma
L17	Paths, Cycles, and Connectivity —
L18	Trees and Spanning Trees —
L19	Eulerian Circuits Euler's theorem on circuits
L20	Hamiltonian Cycles and Why They Are Harder Euler's theorem on circuits
L21	Bipartite Graphs and Matchings —
L22	Graph Colouring —
L23	Boolean Algebra and Logic Circuits —
L24	Synthesis: Counting, Structure, and Algorithm The inclusion–exclusion principle, The handshaking lemma