How It Works
Courses
Login
JOIN BETA

Discrete Mathematics

This course is currently under construction. The target release date for this course is February.
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.

Outcomes

Content

Logic

Number Theory

Probability & Combinatorics

Sequences & Recursion

Graph Theory

Graph Algorithms

General Algorithms

1.
Boolean Algebra
17 topics
1.1. Boolean Functions
1.1.1. Boolean Functions
1.1.2. Boolean Functions And Logical Operations
1.1.3. Disjunctive Normal Forms
1.1.4. Conjunctive Normal Forms
1.1.5. Zhegalkin Polynomials
1.2. Classes of Boolean Functions
1.2.1. Truth-Preserving Boolean Functions
1.2.2. Falsity-Preserving Boolean Functions
1.2.3. Self-Dual Boolean Functions
1.2.4. Monotonic Boolean Functions
1.2.5. Affine Boolean Functions
1.2.6. Post's Functional Completeness Theorem
1.3. Logic Circuits
1.3.1. Introduction to Logic Circuits
1.3.2. Simplifying Logic Circuits
1.3.3. Logic Gates and Combinational Circuits
1.3.4. Simplifying Combinational Circuits
1.3.5. Simplifying Logical Expressions Using Karnaugh Maps
1.3.6. Simplifying Logical Expressions Using Quine-McCluskey Algorithm
2.
Number Theory
17 topics
2.4. Numbers in Different Bases
2.4.1. Binary Integers
2.4.2. Adding and Subtracting Binary Integers
2.4.3. Multiplying and Dividing Binary Integers
2.4.4. Binary Floating Point Fractions
2.4.5. Hexadecimal Integers
2.4.6. Converting Between Binary and Hexadecimal
2.4.7. Integers in Arbitrary Bases
2.4.8. Floating Point Fractions in Arbitrary Bases
2.5. Fermat and Euler's Theorems
2.5.1. Fermat's Little Theorem
2.5.2. Euler's Totient Function
2.5.3. Euler's Theorem
2.6. Cryptography
2.6.1. The Caesar Cipher
2.6.2. The Linear Cipher
2.6.3. Diffie-Hellman Shared Secret Exchange Protocol
2.6.4. RSA Cryptosystem
2.6.5. Rabin Cryptosystem
2.6.6. ElGamal Cryptosystem
3.
Probability & Combinatorics
23 topics
3.7. Discrete Random Variables
3.7.1. Probability Mass Functions of Discrete Random Variables
3.7.2. Cumulative Distribution Functions for Discrete Random Variables
3.7.3. Expected Values of Discrete Random Variables
3.7.4. The Binomial Distribution
3.7.5. Modeling With the Binomial Distribution
3.7.6. The Geometric Distribution
3.7.7. Modeling With the Geometric Distribution
3.7.8. The Discrete Uniform Distribution
3.7.9. Modeling With the Discrete Uniform Distribution
3.7.10. The Poisson Distribution
3.7.11. Modeling With the Poisson Distribution
3.7.12. The Negative Binomial Distribution
3.7.13. Modeling With the Negative Binomial Distribution
3.8. Bayes' Theorem
3.8.1. Introduction to Bayes' Theorem
3.8.2. Generalizing Bayes' Theorem
3.9. Combinatorics
3.9.1. Permutations With Repetition
3.9.2. Applications of the Multinomial Theorem
3.9.3. K Permutations of N With Repetition
3.9.4. Combinations With Repetition
3.9.5. The Inclusion-Exclusion Principle
3.9.6. Counting Integer Solutions of a Constrained Equation
3.9.7. Applications of Combinatorics
3.9.8. Partitions
4.
Sequences & Recursion
22 topics
4.10. Working With Geometric Series
4.10.1. Infinite Series and Partial Sums
4.10.2. Finding the Sum of an Infinite Geometric Series
4.10.3. Writing an Infinite Geometric Series in Sigma Notation
4.10.4. Finding the Sum of an Infinite Geometric Series Expressed in Sigma Notation
4.11. The Generalized Binomial Theorem
4.11.1. Introduction to the Generalized Binomial Theorem
4.11.2. Working With the Generalized Binomial Theorem
4.11.3. Determining the Range of Validity for a Generalized Binomial Expansion
4.11.4. Approximating Numerical Values Using the Generalized Binomial Theorem
4.12. The Multinomial Theorem
4.12.1. The Multinomial Theorem
4.12.2. Calculating the Number of Terms in a Multinomial Expansion
4.13. Recurrence Relations
4.13.1. Introduction to Recurrence Relations
4.13.2. First-Order Recurrence Relations
4.13.3. Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Distinct Real Roots
4.13.4. Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Repeated Roots
4.13.5. Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Complex Roots
4.13.6. Second-Order Recurrence Relations with Polynomial Forcing
4.13.7. Second-Order Recurrence Relations with Exponential Forcing
4.14. Generating Functions
4.14.1. Generating Functions
4.14.2. Generating Functions of Homogeneous Recurrence Relations
4.14.3. Determining the General Term of a Sequence Given Its Generating Function
4.14.4. Generating Functions for Inhomogeneous Recurrence Relations
4.14.5. Solving Recurrence Relations using Generating Functions
6.
Graph Theory
35 topics
6.15. Introduction to Graph Theory
6.15.1. Introduction to Graphs
6.15.2. Edges and Vertices
6.15.3. The Degree of a Vertex
6.15.4. The Handshaking Lemma
6.15.5. Subgraphs
6.16. Types of Graphs
6.16.1. Weighted Graphs
6.16.2. Simple Graphs
6.16.3. Directed Graphs
6.16.4. Directed Acyclic Graphs
6.16.5. Complete Graphs
6.16.6. Regular Graphs
6.16.7. Platonic Graphs
6.16.8. Graph Complements
6.16.9. Bipartite Graphs
6.16.10. Complete Bipartite Graphs
6.16.11. Isomorphic Graphs
6.16.12. Graph Automorphisms
6.16.13. Planar Graphs
6.17. Matrix Representations of Graphs
6.17.1. Incidence Matrices
6.17.2. Adjacency Matrices
6.17.3. Distance Matrices
6.18. Connectivity in Graphs
6.18.1. Paths, Walks, and Trails
6.18.2. Cycles in Graphs
6.18.3. Girth
6.18.4. Connected Graphs
6.18.5. Connected Components
6.18.6. Cut Edges
6.18.7. Cut Vertices
6.19. Graph Algorithms
6.19.1. Breadth-First Search
6.19.2. Depth-First Search
6.20. Trees
6.20.1. Trees and Forests
6.20.2. Counting Trees
6.20.3. Spanning Trees
6.20.4. Counting Spanning Trees
6.20.5. Minimum Spanning Trees
7.
Algorithms on Graphs
37 topics
7.21. Spanning Tree Algorithms
7.21.1. Kruskal's Algorithm
7.21.2. Prim's Algorithm
7.21.3. Applying Prim's Algorithm to a Distance Matrix
7.22. Shortest Path Algorithms
7.22.1. Shortest Paths in Unweighted Graphs
7.22.2. Shortest Paths in Weighted Graphs
7.22.3. The Bellman-Ford Algorithm
7.22.4. Dijkstra's Algorithm
7.22.5. A* Search
7.23. Eulerian Tours
7.23.1. Eulerian Graphs
7.23.2. Semi-Eulerian Graphs
7.23.3. Fleury's Algorithm
7.23.4. The Chinese Postman Algorithm Applied to Eulerian Graphs
7.23.5. The Chinese Postman Algorithm Applied to Semi-Eulerian Graphs
7.24. Hamiltonian Graphs
7.24.1. Hamiltonian Cycles and Tours
7.24.2. Hamiltonian Graphs
7.24.3. The Traveling Salesperson Problem
7.24.4. Computing Upper Bounds for the Traveling Salesperson Problem
7.24.5. Computing Lower Bounds for the Traveling Salesperson Problem
7.24.6. The Nearest Neighbor Algorithm
7.25. Critical Path Analysis
7.25.1. Modeling a Project Using an Activity Network
7.25.2. Using Dummy Activities in Activity Networks
7.25.3. Applying Forward and Backward Passes to Activity Networks
7.25.4. Identifying Critical Activities in Activity Networks
7.25.5. Determining Floats in Activity Networks
7.25.6. Constructing Gantt Charts
7.25.7. Using Gantt Charts to Solve Problems
7.25.8. Scheduling Diagrams
7.26. Matchings
7.26.1. Matchings in Bipartite Graphs
7.26.2. The Maximum Matching Algorithm
7.26.3. Matchings in General Graphs
7.27. Network Flows
7.27.1. Introduction to Network Flows
7.27.2. Cuts in Networks
7.27.3. Finding Initial Flows Through Networks
7.27.4. Increasing Flows Through Networks
7.27.5. Menger's Theorem
7.27.6. The Maximum-Flow Minimum-Cut Theorem
7.27.7. Increasing Flows Through Networks With Multiple Sources/Sinks
8.
The Theory of Algorithms
18 topics
8.28. Finite-State Transducers
8.28.1. Mealy Machines
8.28.2. Moore Machines
8.29. Finite-State Interceptors
8.29.1. Deterministic Finite Automata
8.29.2. Nondeterministic Finite Automata
8.29.3. Finite Automata With Epsilon Transitions
8.29.4. Regular Expressions
8.29.5. Context-Free Grammars
8.29.6. Introduction to Turing Machines
8.29.7. Nondeterministic Turing Machines
8.29.8. Undecidable Problems
8.30. Algorithmic Complexity
8.30.1. Defining Big-O Notation
8.30.2. Properties of Big-O Notation
8.30.3. Defining Big-Omega Notation
8.30.4. Properties of Big-Omega Notation
8.30.5. Defining Theta Notation
8.30.6. Properties Theta Notation
8.30.7. Time Complexity of Mathematical Procedures
8.30.8. P vs. NP Problems