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

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.

- Evaluate boolean logic expressions and convert to normal forms.
- Identify and reason about properties of boolean functions, including completeness.
- Translate between logical expressions and circuits and apply rules of logic to simplify circuits.

- Perform arithmetic with binary numbers and convert between floating point fractions numbers in arbitrary bases.
- Compute modular residues of large exponents using Euler's theorem.
- Encode/decode messages using various cryptosystems.

- Compute the cumulative distribution and expected value given the probability distribution of a discrete random variable.
- Understand the properties of various families of discrete probability distributions and apply appropriate distributions to solve real-world modeling problems.
- Compute conditional probabilities using Bayes’ theorem and apply them in modeling contexts.
- Apply combinatorial shortcuts to quickly solve counting problems for which manual enumeration would otherwise be infeasible.
- Use the generalized binomial theorem to approximate reciprocal, radical, and rational functions.
- Expand multinomials using the multinomial theorem.

- Reason about infinite geometric series and compute the sum if convergent.
- Use the superposition principle in conjunction with the characteristic equation to solve homogeneous recurrence relations.
- Interpret the right-hand side of an inhomogeneous recurrence relation as a forcing function, and use the method of undetermined coefficients to find particular solutions for various types of forcing functions.
- Convert between recurrence relations and generating functions and use generating functions to solve recurrence relations.

- Describe graphs using proper terminology including edges, vertices, paths, cycles, subgraphs, vertex degree, edge weight, and edge direction.
- Identify and reason about graphs with special properties including simple, complete, regular, platonic, bipartite, planar, connected, Eulerian, and Hamiltonian graphs.
- Determine whether two graphs are isomorphic and count the automorphisms of a graph.
- Construct and interpret matrix representations of graphs, including incidence, adjacency, and distance matrices.
- Count the connected components of a graph and identify cut edges and cut vertices.

- Perform breadth-first and depth-first traversals.
- Use well-known algorithms to compute spanning trees (Kruskal, Prim), shortest paths (Bellman-Ford, Dijkstra, A* Search), and Eulerian tours (Fleury, Chinese Postman).
- Solve the traveling salesperson problem approximately using the nearest neighbor algorithm.
- Apply graph algorithms to reason about real-world problems in the context of project management, including analyzing critical paths in activity networks.
- Carry out the maximum matching algorithm and the max-flow min-cut algorithm.

- Identify and reason about types of state machines, including Turing machines.
- Define and derive big-O, big-Omega, and theta time complexities for various algorithms.
- Reason about decidability and the complexity classes P and NP.

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 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 Discrete Uniform Distributions | |

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. | Bayes' Theorem | |

3.8.2. | Extending 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 |