Discrete Mathematics
The mathematics of computing and networks: what discrete questions look like and why small cases can mislead, the sum and product rules, the pigeonhole principle and the birthday problem, permutations, combinations, multinomial coefficients and stars and bars, binomial coefficients, Pascal's triangle and combinatorial identities proved by double counting, recurrence relations from the Tower of Hanoi to Fibonacci numbers and tilings, solving linear recurrences with the characteristic equation and Binet's formula, graphs with their degrees, families, isomorphism and adjacency matrices, connectivity, bipartite graphs and Euler and Hamilton circuits, trees, Cayley's formula and minimum spanning trees with Kruskal and Prim, shortest paths with breadth-first search, Dijkstra, Bellman–Ford and Floyd–Warshall, divisibility, Euclid's algorithm, modular arithmetic and Fermat's little theorem, and a capstone on designing a reliable network and securing it with RSA, with runnable Python examples throughout.
MATH-260 Year 2 3 credits 12 lessons · 4 h 43 min ▶ Video lessons coming soon
Offered by HSM University · Mathematics & Statistics
What you'll learn
- Read and write sum and product notation, recognize the four kinds of discrete question (existence, counting, optimization and structure), and explain why checking small cases cannot replace a proof.
- Apply the sum and product rules, two-set inclusion–exclusion and the generalized pigeonhole principle to count strings, passwords, divisors and subsets, and estimate collision probabilities with the birthday calculation.
- Count arrangements and selections with permutations, combinations, multinomial coefficients and stars and bars, and choose the correct formula according to whether order matters and repetition is allowed.
- Prove binomial identities, including Pascal’s rule, Vandermonde’s identity and the hockey-stick identity, both algebraically and by double counting, and use the binomial theorem to expand and evaluate sums.
- Model counting and algorithmic problems with recurrence relations, including the Tower of Hanoi, Fibonacci numbers, tilings and bit strings, and compute their values efficiently with iteration or memoization.
- Solve linear homogeneous recurrences with constant coefficients by the characteristic equation, handle repeated roots and simple non-homogeneous terms, and derive and use Binet’s formula.
- Use graph vocabulary precisely, apply the handshake lemma, test degree sequences with Havel–Hakimi, decide simple isomorphism questions, and represent graphs by adjacency matrices and lists.
- Find components and test bipartiteness with breadth-first search, identify bridges, prove and apply Euler’s theorem on circuits and trails, and explain why Hamilton cycles are hard to decide.
- Prove the basic properties of trees, count labelled trees with Cayley’s formula and Prüfer codes, and find minimum spanning trees with Kruskal’s and Prim’s algorithms justified by the cut property.
- Compute shortest paths with breadth-first search and Dijkstra’s algorithm, prove Dijkstra correct for nonnegative lengths, and recognize when Bellman–Ford or Floyd–Warshall is needed.
- Use the division algorithm, Euclid’s algorithm and Bézout’s identity, compute modular inverses and fast modular powers, and apply Fermat’s little theorem and Euler’s theorem.
- Combine counting, graph algorithms and number theory to design a reliable, efficiently routed network and explain the correctness and security of RSA encryption and signatures.
Course content
12 lessons · 4 h 43 min total · final exam
- 1 What discrete mathematics is for 24 min · quiz
- 2 Counting principles: sums, products and the pigeonhole principle 25 min · quiz
- 3 Permutations and combinations 23 min · quiz
- 4 Binomial coefficients and Pascal's triangle 21 min · quiz
- 5 Recurrence relations 23 min · quiz
- 6 Solving linear recurrences 25 min · quiz
- 7 Graphs: vocabulary, degrees and representations 25 min · quiz
- 8 Paths, connectivity, Euler and Hamilton 24 min · quiz
- 9 Trees and spanning trees 23 min · quiz
- 10 Shortest paths and graph algorithms 23 min · quiz
- 11 Number theory basics: divisibility, gcd and modular arithmetic 23 min · quiz
- 12 Capstone: the mathematics of a secure network 24 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
The mathematics of computing and networks: what discrete questions look like and why small cases can mislead, the sum and product rules, the pigeonhole principle and the birthday problem, permutations, combinations, multinomial coefficients and stars and bars, binomial coefficients, Pascal's triangle and combinatorial identities proved by double counting, recurrence relations from the Tower of Hanoi to Fibonacci numbers and tilings, solving linear recurrences with the characteristic equation and Binet's formula, graphs with their degrees, families, isomorphism and adjacency matrices, connectivity, bipartite graphs and Euler and Hamilton circuits, trees, Cayley's formula and minimum spanning trees with Kruskal and Prim, shortest paths with breadth-first search, Dijkstra, Bellman–Ford and Floyd–Warshall, divisibility, Euclid's algorithm, modular arithmetic and Fermat's little theorem, and a capstone on designing a reliable network and securing it with RSA, with runnable Python examples throughout.
Part of the Science stream, typically taken in year 2.