How It Works
Courses
Pedagogy
FAQ
About Us
Login
JOIN BETA

Discrete Mathematics

This course is currently under construction. The target release date for this course is unspecified.

Overview

Outcomes

Content

Learn mathematical techniques for reasoning about quantities that are discrete rather than continuous. Encounter graphs, algorithms, and other areas of math that are widely applicable in computer science.

Upon successful completion of this course, students will have mastered the following:

Logic

Number Theory

Probability & Combinatorics

Sequences & Recursion

Graph Theory

Graph Algorithms

General Algorithms

1.
Preliminaries
7 topics
1.1. Sets
1.1.1. Partial Order
1.1.2. Properties of Elements in Posets
1.1.3. The Pigeonhole Principle
1.2. Linear Algebra
1.2.1. Systems of Equations as Augmented Matrices
1.2.2. Row Echelon Form
1.2.3. Solving Systems of Equations Using Back Substitution
1.2.4. Symmetric Matrices
2.
Boolean Algebra
17 topics
2.3. Boolean Functions
2.3.1. Boolean Functions
2.3.2. Boolean Functions And Logical Operations
2.3.3. Disjunctive Normal Forms
2.3.4. Principal Disjunctive Normal Forms
2.3.5. Conjunctive Normal Forms
2.3.6. Principal Conjunctive Normal Forms
2.3.7. Boolean Polynomials
2.3.8. Simplifying Logical Expressions Using Karnaugh Maps
2.4. Classes of Boolean Functions
2.4.1. Truth-Preserving Boolean Functions
2.4.2. Self-Dual Boolean Functions
2.4.3. Monotonic Boolean Functions
2.4.4. Affine Boolean Functions
2.4.5. Functionally Complete Sets
2.4.6. Post's Functional Completeness Theorem
2.5. Logic Circuits
2.5.1. Introduction to Logic Circuits
2.5.2. Logic Gates and Combinational Circuits
2.5.3. Simplifying Logic Circuits
3.
Number Theory
15 topics
3.6. Numbers in Different Bases
3.6.1. Binary Integers
3.6.2. Adding and Subtracting Binary Integers
3.6.3. Multiplying and Dividing Binary Integers
3.6.4. Binary Fractions
3.6.5. Hexadecimal Integers
3.6.6. Converting Between Binary and Hexadecimal
3.6.7. Integers in Arbitrary Bases
3.6.8. Floating Point Fractions in Arbitrary Bases
3.7. Fermat and Euler's Theorems
3.7.1. Fermat's Little Theorem
3.7.2. Euler's Totient Function
3.7.3. Euler's Theorem
3.8. Cryptography
3.8.1. The Caesar Cipher
3.8.2. The Linear Cipher
3.8.3. Diffie-Hellman Shared Secret Exchange Protocol
3.8.4. RSA Cryptosystem
4.
Probability & Combinatorics
39 topics
4.9. Discrete Random Variables
4.9.1. Probability Mass Functions of Discrete Random Variables
4.9.2. Cumulative Distribution Functions for Discrete Random Variables
4.9.3. One-to-One Transformations of Discrete Random Variables
4.9.4. Many-to-One Transformations of Discrete Random Variables
4.9.5. Expected Values of Discrete Random Variables
4.9.6. Properties of Expectation for Discrete Random Variables
4.9.7. Variance of Discrete Random Variables
4.9.8. Moments of Discrete Random Variables
4.9.9. Properties of Variance for Discrete Random Variables
4.10. The Discrete Uniform Distribution
4.10.1. The Discrete Uniform Distribution
4.10.2. Mean and Variance of the Discrete Uniform Distribution
4.10.3. Modeling With Discrete Uniform Distributions
4.11. The Bernoulli Distribution
4.11.1. The Bernoulli Distribution
4.11.2. Mean and Variance of the Bernoulli Distribution
4.12. The Binomial Distribution
4.12.1. The Binomial Distribution
4.12.2. Modeling With the Binomial Distribution
4.12.3. Mean and Variance of the Binomial Distribution
4.13. The Poisson Distribution
4.13.1. The Poisson Distribution
4.13.2. Modeling With the Poisson Distribution
4.13.3. Mean and Variance of the Poisson Distribution
4.13.4. The Poisson Approximation of the Binomial Distribution
4.14. The Geometric Distribution
4.14.1. The Geometric Distribution
4.14.2. Modeling With the Geometric Distribution
4.14.3. Mean and Variance of the Geometric Distribution
4.15. The Negative Binomial Distribution
4.15.1. The Negative Binomial Distribution
4.15.2. Modeling With the Negative Binomial Distribution
4.16. The Hypergeometric Distribution
4.16.1. The Hypergeometric Distribution
4.16.2. The PMF of the Hypergeometric Distribution
4.17. Bayes' Theorem
4.17.1. Bayes' Theorem
4.17.2. Extending Bayes' Theorem
4.17.3. The Law of Total Probability
4.17.4. Extending the Law of Total Probability
4.18. Combinatorics
4.18.1. Permutations With Repetition
4.18.2. Applications of the Multinomial Theorem
4.18.3. K Permutations of N With Repetition
4.18.4. Combinations With Repetition
4.18.5. The Inclusion-Exclusion Principle
4.18.6. Counting Integer Solutions of a Constrained Equation
4.18.7. Partitions
5.
Sequences
14 topics
5.19. Finite Series
5.19.1. Finite Linear Series
5.19.2. Finite Quadratic Series
5.19.3. Finite Cubic Series
5.20. Geometric Series
5.20.1. Infinite Series and Partial Sums
5.20.2. Convergent and Divergent Infinite Series
5.20.3. Finding the Sum of an Infinite Geometric Series
5.20.4. Writing an Infinite Geometric Series in Sigma Notation
5.20.5. Sums of Infinite Geometric Series Given in Sigma Notation
5.21. The Generalized Binomial Theorem
5.21.1. Introduction to the Generalized Binomial Theorem
5.21.2. Working With the Generalized Binomial Theorem
5.21.3. Determining Ranges of Validity for Generalized Binomial Expansions
5.21.4. Approximating Values Using the Generalized Binomial Theorem
5.22. The Multinomial Theorem
5.22.1. The Multinomial Theorem
5.22.2. Calculating the Number of Terms in a Multinomial Expansion
6.
Recursion
15 topics
6.23. Recurrence Relations
6.23.1. Introduction to Recurrence Relations
6.23.2. First-Order Recurrence Relations
6.23.3. First-Order Recurrence Relations With Polynomial Forcing
6.23.4. First-Order Recurrence Relations With Exponential Forcing
6.23.5. Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Distinct Real Roots
6.23.6. Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Repeated Roots
6.23.7. Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Complex Roots
6.23.8. Second-Order Recurrence Relations with Polynomial Forcing
6.23.9. Second-Order Recurrence Relations with Exponential Forcing
6.24. Generating Functions
6.24.1. Generating Functions
6.24.2. Generating Functions of Homogeneous Recurrence Relations
6.24.3. Determining the General Term of a Sequence Given Its Generating Function
6.24.4. Generating Functions for Inhomogeneous Recurrence Relations
6.24.5. Solving Homogeneous Recurrence Relations Using Generating Functions
6.24.6. Solving Inhomogeneous Recurrence Relations Using Generating Functions
7.
Graph Theory
28 topics
7.25. Introduction to Graph Theory
7.25.1. Introduction to Graphs
7.25.2. Walks, Trails, Paths, and Distances
7.25.3. Walks, Paths, and Distances in Directed Graphs
7.25.4. The Degree of a Vertex
7.25.5. The Handshaking Lemma
7.25.6. Subgraphs and Graph Complements
7.25.7. Complete and Bipartite Graphs
7.25.8. Regular Graphs
7.25.9. Planar Graphs
7.26. Connectivity in Graphs
7.26.1. Cycles in Graphs
7.26.2. Connected Graphs
7.26.3. Cut Vertices and Cut Edges
7.27. Trees
7.27.1. Trees and Forests
7.27.2. Counting Trees
7.28. Matrix Representations of Graphs
7.28.1. Incidence Matrices
7.28.2. Adjacency Matrices
7.28.3. Adjacency Matrices of Directed Graphs
7.28.4. Distance Matrices
7.29. DAGs and Topological Sorting
7.29.1. Directed Acyclic Graphs
7.29.2. Topological Ordering
7.29.3. Kahn's Algorithm for Topological Ordering
7.30. Algorithms on Graphs
7.30.1. Breadth-First Search
7.30.2. Depth-First Search
7.30.3. Kruskal's Algorithm
7.30.4. Prim's Algorithm
7.30.5. Applying Prim's Algorithm to a Distance Matrix
7.30.6. Shortest Paths in Unweighted Graphs
7.30.7. Dijkstra's Algorithm
8.
The Theory of Algorithms
14 topics
8.31. Finite-State Transducers
8.31.1. Mealy Machines
8.31.2. Moore Machines
8.32. Finite-State Interceptors
8.32.1. Deterministic Finite Automata
8.32.2. Extending the Transition Function of a DFA to Strings
8.32.3. Nondeterministic Finite Automata
8.32.4. The Language of Automata
8.32.5. Regular Expressions
8.32.6. Context-Free Grammars
8.32.7. Introduction to Turing Machines
8.32.8. Working With Turing Machines
8.32.9. Nondeterministic Turing Machines
8.33. Algorithmic Complexity
8.33.1. Big-O Notation
8.33.2. Big-Omega Notation
8.33.3. Theta Notation