Welcome to the main Discrete Mathematics page. To go to a specific course, please click on the one of the links under the Discrete Mathematics tab above. No calculators required for this course! Here’s a description of course topics.
Set Theory – We begin by introducing sets. We discuss Cartesian Products, Power Sets, Operations, Subsets, and the Well Ordering Principle. This is the foundation of all of Discrete Mathematics.
Logic – This is a hyper-introduction to Propositional and Predicate Logic. Proofs are done by truth tables and basic rules of inference. We quickly touch on Predicate Logic and define the quantifiers a little more intuitively than most textbooks.
Counting – Although basic counting is simple, we look at the many ways that we can arrange people at tables, how many ways we can distribute books to children, and how many integer solutions there are to specific equations. We also look at the Binomial Distribution, which is incredibly important for fast expansion of polynomials.
Proof Techniques – Without proof techniques, you would never learn real mathematics. Although only simple proofs are done in the course, we introduce methods so in later courses you’re able to jump right into proofs without much difficulty.
Relations and Functions – We briefly touch on relations and functions. What is a function? What does it mean to be one-to-one, onto, bijective, or have inverse functions? What is symmetry, reflexivity, transitivity?
Number Theory – After introducing the pigeonhole principle, we discuss divisibility, prime numbers, greatest common divisors, and the Euclidian Algorithm. This is probably the most computational component in the course.
Formal Languages – We touch on formal languages and finite state machines. This introduction is very brief, but gives a basic overview of what’s to come in future courses. If demand is high to continue, I will probably do an entire separate course on this topic. Formal Languages are very involved and are very fun.
Probability – We look at finite probability and conditional probability. This is nothing too difficult, and is no more involved than an introductory statistics course.
Inclusion-Exclusion Principle – This is an important topic that covers derangements as well. What is a derangement? Well, consider 20 students take a test. How many ways can we have the tests marked so that no student is marking his own test? What is the probability that this can happen?
Generating Functions – Suppose our conditions on counting are a little bit stricter, and our questions are a little bit more challenging. How can we find the number of ways to do something that sounds so complicated? We introduce generating functions that produce power series, where each coefficient is the number of ways to complete some item of length n.
Recurrence Relations – We look at relationships between numbers. In a recurrence relation, the n-th number depends on some combination of previous numbers in the sequence. We look at solutions of recurrence relations, both homogeneous and non-homogeneous, as well as some word problems. We also take a look at how we can solve recurrence relations with Generating Functions.
Graph Theory – We cover a huge variety of basic topics and terminology in graph theory. We take a look at walks, trails, paths, circuits, cycles, Eulerian trails, Hamilton paths, subgraphs, isomorphisms, planar graphs, and relevant proofs.
Optimization and Matching – Another topic in Graph Theory, but we move into a very specific type of graphs – trees. We introduce trees, their properties, and then move into shortest path algorithms. Specifically, we look at Dijkstra’s algorithm.
Extra Content – Upon request, I added videos on flow networks and minimal cuts.