Course

Discrete mathematics

You will learn to prove by induction, count configurations, reason with relations and graphs, and solve recurrences and congruences. It is the foundation for computer science, algorithms and cryptography.

Recommended before this course: Probability and statistics (1 concept comes from that course and is tagged)

33concepts

5topics

330exercises

≈ 17 hof study approx.

Start course →⏱ Exam simulator

Course path

1
Proofs and induction 4 concepts
Direct proof · Proof by contradiction · Mathematical induction · Strong induction
2
Sets and relations 4 concepts
Set operations · Inclusion-exclusion principle · Partial order relation · Hasse diagram
3
Counting 8 concepts
Permutations and combinations from Probability and statistics · Multiplication principle · Factorial · Permutations with repetition · Pigeonhole principle · Binomial coefficient · Binomial theorem · Combinations with repetition
4
Graph theory 10 concepts
Graph · Degree of a vertex · Path in a graph · Connected graph · Tree · Eulerian cycle · Hamiltonian cycle · Bipartite graph · Graph coloring · Planar graph
5
Recurrences and arithmetic 7 concepts
Recurrence relation · Divisibility · Greatest common divisor · Euclidean algorithm · Modular congruence · Homogeneous linear recurrence · Prime number

Sources

Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019.
Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019.
László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond, 1st edition, Springer, 2003.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003.
Joseph K. Blitzstein, Jessica Hwang, Introduction to Probability, 2nd edition, CRC Press, 2019.
Sheldon Ross, A First Course in Probability, 10th edition, Pearson, 2019.
Larry Wasserman, All of Statistics, 1st edition, Springer, 2004.