Our Discrete Mathematics course is the second in a two-part series, building on many key concepts encountered in our Methods of Proof course.
Throughout this course, students will develop theoretical and practical knowledge of Boolean algebra, number theory, probability and combinatorics, sequences and recursion, graph theory, and the theory of algorithms.
Designed for students pursuing careers in computer science, mathematics, engineering, machine learning, and data science, it provides a strong theoretical foundation for modern computing systems while enhancing mathematical reasoning and problem-solving skills.
Students will deepen their understanding of logic by exploring Boolean functions and logic circuits, which are fundamental in modern digital systems. They will learn to analyze and simplify Boolean functions, applying these skills to optimize digital circuit design.
This course further develops various number theory concepts encountered in our Methods of Proof course. Students will study different number bases (including binary and hexadecimal) and learn how linear congruences form the backbone of modern cryptographic protocols like Diffie-Hellman and RSA.
Probability is crucial in many real-world applications. This course covers fundamental topics such as elementary probability, random variables, expectation algebra, discrete probability distributions, and combinatorics. Real-world examples are integrated throughout, helping students connect theory to practice.
Students will explore sequences and series, covering topics such as finite sums, geometric series, and the generalized binomial and multinomial theorems. Students will also study first and second-order recurrence relations and learn how generating functions can be used to find solutions to these relations. Graphs are a fundamental part of modern computing systems. Students will explore graph theory, prove key properties of graphs, and study essential graph traversal algorithms, including breadth-first and depth-first search, spanning tree algorithms, and Dijkstra's algorithm. Finally, students learn about the theory underpinning modern computer algorithms. They will study theoretical mathematical machines (acceptors, transducers, and Turing machines) and asymptotic notation to describe an algorithm's complexity.
Understanding the concept of a Boolean function, including their representations, composition, equivalence, and counting the number of Boolean functions on N variables.
Understanding the definitions of exclusive disjunction (XOR), Peirce arrow (NOR), Sheffer Stroke (NAND), and simplifying Boolean expressions involving these operations.
Understanding disjunctive and conjunctive normal forms and expressing Boolean functions in principle disjunctive and conjunctive normal forms.
Working with Boolean polynomials, including simplifying them and proving various properties related to these polynomials.
Using Karnaugh maps to express a Boolean function in minimal disjunctive normal form.
Understanding the concepts of truth-preservation, self-duality, monotonicity, and affineness in relation to Boolean functions.
Applying Post's theorem to determine whether a set of Boolean functions is functionally complete.
Representing a logic circuit using Boolean functions and simplifying logic circuits.
The binary system of numbers, including converting between binary and decimal representations of integers, adding, subtracting, multiplying, and dividing binary integers, and representations of binary fractions.
Systems of numbers in arbitrary bases, including hexadecimal numbers.
Understanding and applying Fermat's little theorem.
Working with Euler's totient function and its properties and applying Euler's theorem.
Cryptography fundamentals, including the Caesar and linear ciphers, the Diffie-Hellman protocol, and the RSA cryptosystem.
Understanding and applying the law of total probability and Bayes' Theorem.
Working with probability mass functions and cumulative distribution functions for discrete random variables.
Calculating expected values, variance, and moments for discrete random variables.
Understanding and applying properties of expectation and variance.
Constructing and applying the probability mass function (PMF) and cumulative distribution function (CDF) of well-known probability distributions, including:
The discrete uniform distribution
The Bernoulli distribution
The binomial distribution
The Poisson distribution
The geometric distribution
The negative binomial distribution
The hypergeometric distribution
Understanding the relationship between the Bernoulli and binomial distributions and the geometric and negative binomial distributions.
Solving real-world situations using these distributions and understanding the conditions where modeling with a known distribution is appropriate.
Approximating a binomial random variable using a Poisson distribution.
Calculating permutations and combinations, including cases with repetition, and modeling real-world and mathematical problems using combinatorial techniques.
Understanding and applying the inclusion-exclusion and pigeonhole principles and constructing partitions of natural numbers.
Calculating sums of finite linear, quadratic, and cubic series.
Working with infinite geometric series and testing for convergence.
Working with the generalized binomial theorem, including calculating the range of validity of a given expansion and using a binomial expansion to estimate a given number.
Applying the multinomial theorem and counting the number of terms in a multinomial expansion.
Understanding the concept of a recurrence relation and fully classifying a given relation.
Solving first and second-order homogeneous recurrence relations using the characteristic equation method.
Solving first and second-order inhomogeneous recurrence relations using the unknown coefficients method.
Understanding the concept of a generating function and using them to solve homogeneous recurrence relations.
Working with generating functions of inhomogeneous recurrence relations.
Understanding the concept of a graph and basic graph terminology, including graph isomorphism, connectivity, subgraphs, walks, paths, trails, and distances in undirected and directed graphs.
Understanding and applying the degree sum formula and proving the handshaking lemma.
Working with complete, bipartite, planar, and regular graphs.
Trees, spanning trees, and finding minimum spanning trees by inspection.
Counting the number of labeled trees, rooted trees, and rooted forests on N vertices.
Representing graphs using incidence, adjacency, and distance matrices.
Understanding the concepts of directed acyclic graphs (DAG) and topological orderings.
Applying Kahn's algorithm to find a topological ordering of a DAG.
Applying the graph-traversal algorithms of the breadth-first search (BFS) and depth-first search (DFS).
Kruskal's and Prim's algorithms are applied to find minimum spanning trees, including Prim's algorithm on a distance matrix.
Applying BFS to find shortest distances in unweighted graphs and Dijkstra's algorithm in weighted graphs.
Understanding the difference between finite-state transducers and acceptors.
Representing Mealy and Moore machines using various methods and processing strings using these machines.
Understanding the difference between deterministic and nondeterministic finite automata, representing them in various forms, and processing strings using these machines.
Describing the language of simple automata and regular expressions.
Representing Turing machines using various methods and processing strings using these machines.
Understanding and applying the definition of Big-O, Big-Omega, and Big-Theta in the context of algorithmic complexity.
1.1.1. | Systems of Equations as Augmented Matrices | |
1.1.2. | Row Echelon Form | |
1.1.3. | Solving Systems of Equations Using Back Substitution | |
1.1.4. | Symmetric Matrices |
2.2.1. | Boolean Functions | |
2.2.2. | Boolean Functions And Logical Operations | |
2.2.3. | Disjunctive Normal Forms | |
2.2.4. | Principal Disjunctive Normal Forms | |
2.2.5. | Conjunctive Normal Forms | |
2.2.6. | Principal Conjunctive Normal Forms | |
2.2.7. | Boolean Polynomials | |
2.2.8. | Simplifying Logical Expressions Using Karnaugh Maps |
2.3.1. | Truth-Preserving Boolean Functions | |
2.3.2. | Self-Dual Boolean Functions | |
2.3.3. | Monotonic Boolean Functions | |
2.3.4. | Affine Boolean Functions | |
2.3.5. | Functionally Complete Sets | |
2.3.6. | Post's Functional Completeness Theorem |
2.4.1. | Introduction to Logic Circuits | |
2.4.2. | Logic Gates and Combinational Circuits | |
2.4.3. | Simplifying Logic Circuits |
3.5.1. | Binary Integers | |
3.5.2. | Adding and Subtracting Binary Integers | |
3.5.3. | Multiplying and Dividing Binary Integers | |
3.5.4. | Binary Fractions | |
3.5.5. | Hexadecimal Integers | |
3.5.6. | Converting Between Binary and Hexadecimal Integers | |
3.5.7. | Integers in Arbitrary Bases | |
3.5.8. | Floating Point Fractions in Arbitrary Bases |
3.6.1. | Fermat's Little Theorem | |
3.6.2. | Euler's Totient Function | |
3.6.3. | Euler's Theorem |
3.7.1. | Introduction to Cryptography | |
3.7.2. | The Linear Cipher | |
3.7.3. | The Diffie-Hellman Protocol | |
3.7.4. | The RSA Cryptosystem |
4.8.1. | Probability Mass Functions of Discrete Random Variables | |
4.8.2. | Cumulative Distribution Functions for Discrete Random Variables | |
4.8.3. | One-to-One Transformations of Discrete Random Variables | |
4.8.4. | Many-to-One Transformations of Discrete Random Variables | |
4.8.5. | Expected Values of Discrete Random Variables | |
4.8.6. | Properties of Expectation for Discrete Random Variables | |
4.8.7. | Variance of Discrete Random Variables | |
4.8.8. | Moments of Discrete Random Variables | |
4.8.9. | Properties of Variance for Discrete Random Variables |
4.9.1. | The Discrete Uniform Distribution | |
4.9.2. | Mean and Variance of the Discrete Uniform Distribution | |
4.9.3. | Modeling With Discrete Uniform Distributions |
4.10.1. | The Bernoulli Distribution | |
4.10.2. | Mean and Variance of the Bernoulli Distribution |
4.11.1. | The Binomial Distribution | |
4.11.2. | Modeling With the Binomial Distribution | |
4.11.3. | Mean and Variance of the Binomial Distribution |
4.12.1. | The Poisson Distribution | |
4.12.2. | Modeling With the Poisson Distribution | |
4.12.3. | Mean and Variance of the Poisson Distribution | |
4.12.4. | The Poisson Approximation of the Binomial Distribution |
4.13.1. | The Geometric Distribution | |
4.13.2. | Modeling With the Geometric Distribution | |
4.13.3. | Mean and Variance of the Geometric Distribution |
4.14.1. | The Negative Binomial Distribution | |
4.14.2. | Modeling With the Negative Binomial Distribution |
4.15.1. | The Hypergeometric Distribution | |
4.15.2. | The PMF of the Hypergeometric Distribution |
4.16.1. | Bayes' Theorem | |
4.16.2. | Extending Bayes' Theorem | |
4.16.3. | The Law of Total Probability | |
4.16.4. | Extending the Law of Total Probability |
4.17.1. | Permutations With Repetition | |
4.17.2. | K Permutations of N With Repetition | |
4.17.3. | Combinations With Repetition | |
4.17.4. | The Inclusion-Exclusion Principle | |
4.17.5. | Counting Integer Solutions of a Constrained Equation | |
4.17.6. | Partitions | |
4.17.7. | The Pigeonhole Principle |
5.18.1. | Finite Linear Series | |
5.18.2. | Finite Quadratic Series | |
5.18.3. | Finite Cubic Series |
5.19.1. | Infinite Series and Partial Sums | |
5.19.2. | Convergent and Divergent Infinite Series | |
5.19.3. | Finding the Sum of an Infinite Geometric Series | |
5.19.4. | Writing an Infinite Geometric Series in Sigma Notation | |
5.19.5. | Sums of Infinite Geometric Series Given in Sigma Notation |
5.20.1. | The Generalized Binomial Theorem | |
5.20.2. | Working With the Generalized Binomial Theorem | |
5.20.3. | Determining Ranges of Validity for Generalized Binomial Expansions | |
5.20.4. | Approximating Values Using the Generalized Binomial Theorem | |
5.20.5. | The Multinomial Theorem | |
5.20.6. | Counting Terms in Multinomial Expansions |
6.21.1. | Introduction to Recurrence Relations | |
6.21.2. | First-Order Recurrence Relations | |
6.21.3. | First-Order Recurrence Relations With Polynomial Forcing | |
6.21.4. | First-Order Recurrence Relations With Exponential Forcing |
6.22.1. | Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Distinct Real Roots | |
6.22.2. | Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Repeated Roots | |
6.22.3. | Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Complex Roots | |
6.22.4. | Second-Order Recurrence Relations with Polynomial Forcing | |
6.22.5. | Second-Order Recurrence Relations with Exponential Forcing |
6.23.1. | Generating Functions | |
6.23.2. | Generating Functions of Homogeneous Recurrence Relations | |
6.23.3. | Determining the General Term of a Sequence Given Its Generating Function | |
6.23.4. | Solving Homogeneous Recurrence Relations Using Generating Functions | |
6.23.5. | Generating Functions for Inhomogeneous Recurrence Relations |
7.24.1. | Introduction to Graphs | |
7.24.2. | Walks, Trails, Paths, and Distances | |
7.24.3. | Walks, Paths, and Distances in Directed Graphs | |
7.24.4. | The Degree of a Vertex | |
7.24.5. | The Handshaking Lemma | |
7.24.6. | Subgraphs and Graph Complements | |
7.24.7. | Complete and Bipartite Graphs | |
7.24.8. | Regular Graphs | |
7.24.9. | Planar Graphs |
7.25.1. | Cycles in Graphs | |
7.25.2. | Connected Graphs | |
7.25.3. | Cut Vertices and Cut Edges |
7.26.1. | Trees and Forests | |
7.26.2. | Counting Trees |
7.27.1. | Incidence Matrices | |
7.27.2. | Adjacency Matrices | |
7.27.3. | Adjacency Matrices of Directed Graphs | |
7.27.4. | Distance Matrices |
7.28.1. | Directed Acyclic Graphs | |
7.28.2. | Topological Ordering | |
7.28.3. | Kahn's Algorithm |
7.29.1. | Breadth-First Search | |
7.29.2. | Kruskal's Algorithm | |
7.29.3. | Prim's Algorithm | |
7.29.4. | Applying Prim's Algorithm to a Distance Matrix | |
7.29.5. | Shortest Paths in Unweighted Graphs | |
7.29.6. | Dijkstra's Algorithm |
8.30.1. | Mealy Machines | |
8.30.2. | Moore Machines |
8.31.1. | Deterministic Finite Automata | |
8.31.2. | Processing Strings Using Deterministic Finite Automata | |
8.31.3. | Nondeterministic Finite Automata | |
8.31.4. | The Language of Automata | |
8.31.5. | Regular Expressions |
8.32.1. | Introduction to Turing Machines | |
8.32.2. | Processing Strings Using Turing Machines | |
8.32.3. | Nondeterministic Turing Machines |
8.33.1. | Big-O Notation | |
8.33.2. | Big-Omega Notation | |
8.33.3. | Big-Theta Notation |