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

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.

Preliminaries
1 topics

1.1. Sets

1.1.1. | Partial Order |

2.

Boolean Algebra
17 topics

2.2. Boolean Functions

2.2.1. | Boolean Functions | |

2.2.2. | Boolean Functions And Logical Operations | |

2.2.3. | Disjunctive Normal Forms | |

2.2.4. | Conjunctive Normal Forms | |

2.2.5. | Zhegalkin Polynomials |

2.3. Classes of Boolean Functions

2.3.1. | Truth-Preserving Boolean Functions | |

2.3.2. | Falsity-Preserving Boolean Functions | |

2.3.3. | Self-Dual Boolean Functions | |

2.3.4. | Monotonic Boolean Functions | |

2.3.5. | Affine Boolean Functions | |

2.3.6. | Post's Functional Completeness Theorem |

2.4. Logic Circuits

2.4.1. | Introduction to Logic Circuits | |

2.4.2. | Simplifying Logic Circuits | |

2.4.3. | Logic Gates and Combinational Circuits | |

2.4.4. | Simplifying Combinational Circuits | |

2.4.5. | Simplifying Logical Expressions Using Karnaugh Maps | |

2.4.6. | Simplifying Logical Expressions Using Quine-McCluskey Algorithm |

3.

Number Theory
17 topics

3.5. Numbers in Different Bases

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 | |

3.5.7. | Integers in Arbitrary Bases | |

3.5.8. | Floating Point Fractions in Arbitrary Bases |

3.6. Fermat and Euler's Theorems

3.6.1. | Fermat's Little Theorem | |

3.6.2. | Euler's Totient Function | |

3.6.3. | Euler's Theorem |

3.7. Cryptography

3.7.1. | The Caesar Cipher | |

3.7.2. | The Linear Cipher | |

3.7.3. | Diffie-Hellman Shared Secret Exchange Protocol | |

3.7.4. | RSA Cryptosystem | |

3.7.5. | Rabin Cryptosystem | |

3.7.6. | ElGamal Cryptosystem |

4.

Probability & Combinatorics
23 topics

4.8. Discrete Random Variables

4.8.1. | Probability Mass Functions of Discrete Random Variables | |

4.8.2. | Cumulative Distribution Functions for Discrete Random Variables | |

4.8.3. | Expected Values of Discrete Random Variables | |

4.8.4. | The Binomial Distribution | |

4.8.5. | Modeling With the Binomial Distribution | |

4.8.6. | The Geometric Distribution | |

4.8.7. | Modeling With the Geometric Distribution | |

4.8.8. | The Discrete Uniform Distribution | |

4.8.9. | Modeling With Discrete Uniform Distributions | |

4.8.10. | The Poisson Distribution | |

4.8.11. | Modeling With the Poisson Distribution | |

4.8.12. | The Negative Binomial Distribution | |

4.8.13. | Modeling With the Negative Binomial Distribution |

4.9. Bayes' Theorem

4.9.1. | Bayes' Theorem | |

4.9.2. | Extending Bayes' Theorem |

4.10. Combinatorics

4.10.1. | Permutations With Repetition | |

4.10.2. | Applications of the Multinomial Theorem | |

4.10.3. | K Permutations of N With Repetition | |

4.10.4. | Combinations With Repetition | |

4.10.5. | The Inclusion-Exclusion Principle | |

4.10.6. | Counting Integer Solutions of a Constrained Equation | |

4.10.7. | Applications of Combinatorics | |

4.10.8. | Partitions |

5.

Sequences & Recursion
22 topics

5.11. Working With Geometric Series

5.11.1. | Infinite Series and Partial Sums | |

5.11.2. | Finding the Sum of an Infinite Geometric Series | |

5.11.3. | Writing an Infinite Geometric Series in Sigma Notation | |

5.11.4. | Finding the Sum of an Infinite Geometric Series Expressed in Sigma Notation |

5.12. The Generalized Binomial Theorem

5.12.1. | Introduction to the Generalized Binomial Theorem | |

5.12.2. | Working With the Generalized Binomial Theorem | |

5.12.3. | Determining the Range of Validity for a Generalized Binomial Expansion | |

5.12.4. | Approximating Numerical Values Using the Generalized Binomial Theorem |

5.13. The Multinomial Theorem

5.13.1. | The Multinomial Theorem | |

5.13.2. | Calculating the Number of Terms in a Multinomial Expansion |

5.14. Recurrence Relations

5.14.1. | Introduction to Recurrence Relations | |

5.14.2. | First-Order Recurrence Relations | |

5.14.3. | Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Distinct Real Roots | |

5.14.4. | Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Repeated Roots | |

5.14.5. | Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Complex Roots | |

5.14.6. | Second-Order Recurrence Relations with Polynomial Forcing | |

5.14.7. | Second-Order Recurrence Relations with Exponential Forcing |

5.15. Generating Functions

5.15.1. | Generating Functions | |

5.15.2. | Generating Functions of Homogeneous Recurrence Relations | |

5.15.3. | Determining the General Term of a Sequence Given Its Generating Function | |

5.15.4. | Generating Functions for Inhomogeneous Recurrence Relations | |

5.15.5. | Solving Recurrence Relations using Generating Functions |

7.

Graph Theory
35 topics

7.16. Introduction to Graph Theory

7.16.1. | Introduction to Graphs | |

7.16.2. | Edges and Vertices | |

7.16.3. | The Degree of a Vertex | |

7.16.4. | The Handshaking Lemma | |

7.16.5. | Subgraphs |

7.17. Types of Graphs

7.17.1. | Weighted Graphs | |

7.17.2. | Simple Graphs | |

7.17.3. | Directed Graphs | |

7.17.4. | Directed Acyclic Graphs | |

7.17.5. | Complete Graphs | |

7.17.6. | Regular Graphs | |

7.17.7. | Platonic Graphs | |

7.17.8. | Graph Complements | |

7.17.9. | Bipartite Graphs | |

7.17.10. | Complete Bipartite Graphs | |

7.17.11. | Isomorphic Graphs | |

7.17.12. | Graph Automorphisms | |

7.17.13. | Planar Graphs |

7.18. Matrix Representations of Graphs

7.18.1. | Incidence Matrices | |

7.18.2. | Adjacency Matrices | |

7.18.3. | Distance Matrices |

7.19. Connectivity in Graphs

7.19.1. | Paths, Walks, and Trails | |

7.19.2. | Cycles in Graphs | |

7.19.3. | Girth | |

7.19.4. | Connected Graphs | |

7.19.5. | Connected Components | |

7.19.6. | Cut Edges | |

7.19.7. | Cut Vertices |

7.20. Graph Algorithms

7.20.1. | Breadth-First Search | |

7.20.2. | Depth-First Search |

7.21. Trees

7.21.1. | Trees and Forests | |

7.21.2. | Counting Trees | |

7.21.3. | Spanning Trees | |

7.21.4. | Counting Spanning Trees | |

7.21.5. | Minimum Spanning Trees |

8.

Algorithms on Graphs
37 topics

8.22. Spanning Tree Algorithms

8.22.1. | Kruskal's Algorithm | |

8.22.2. | Prim's Algorithm | |

8.22.3. | Applying Prim's Algorithm to a Distance Matrix |

8.23. Shortest Path Algorithms

8.23.1. | Shortest Paths in Unweighted Graphs | |

8.23.2. | Shortest Paths in Weighted Graphs | |

8.23.3. | The Bellman-Ford Algorithm | |

8.23.4. | Dijkstra's Algorithm | |

8.23.5. | A* Search |

8.24. Eulerian Tours

8.24.1. | Eulerian Graphs | |

8.24.2. | Semi-Eulerian Graphs | |

8.24.3. | Fleury's Algorithm | |

8.24.4. | The Chinese Postman Algorithm Applied to Eulerian Graphs | |

8.24.5. | The Chinese Postman Algorithm Applied to Semi-Eulerian Graphs |

8.25. Hamiltonian Graphs

8.25.1. | Hamiltonian Cycles and Tours | |

8.25.2. | Hamiltonian Graphs | |

8.25.3. | The Traveling Salesperson Problem | |

8.25.4. | Computing Upper Bounds for the Traveling Salesperson Problem | |

8.25.5. | Computing Lower Bounds for the Traveling Salesperson Problem | |

8.25.6. | The Nearest Neighbor Algorithm |

8.26. Critical Path Analysis

8.26.1. | Modeling a Project Using an Activity Network | |

8.26.2. | Using Dummy Activities in Activity Networks | |

8.26.3. | Applying Forward and Backward Passes to Activity Networks | |

8.26.4. | Identifying Critical Activities in Activity Networks | |

8.26.5. | Determining Floats in Activity Networks | |

8.26.6. | Constructing Gantt Charts | |

8.26.7. | Using Gantt Charts to Solve Problems | |

8.26.8. | Scheduling Diagrams |

8.27. Matchings

8.27.1. | Matchings in Bipartite Graphs | |

8.27.2. | The Maximum Matching Algorithm | |

8.27.3. | Matchings in General Graphs |

8.28. Network Flows

8.28.1. | Introduction to Network Flows | |

8.28.2. | Cuts in Networks | |

8.28.3. | Finding Initial Flows Through Networks | |

8.28.4. | Increasing Flows Through Networks | |

8.28.5. | Menger's Theorem | |

8.28.6. | The Maximum-Flow Minimum-Cut Theorem | |

8.28.7. | Increasing Flows Through Networks With Multiple Sources/Sinks |

9.

The Theory of Algorithms
18 topics

9.29. Finite-State Transducers

9.29.1. | Mealy Machines | |

9.29.2. | Moore Machines |

9.30. Finite-State Interceptors

9.30.1. | Deterministic Finite Automata | |

9.30.2. | Nondeterministic Finite Automata | |

9.30.3. | Finite Automata With Epsilon Transitions | |

9.30.4. | Regular Expressions | |

9.30.5. | Context-Free Grammars | |

9.30.6. | Introduction to Turing Machines | |

9.30.7. | Nondeterministic Turing Machines | |

9.30.8. | Undecidable Problems |

9.31. Algorithmic Complexity

9.31.1. | Defining Big-O Notation | |

9.31.2. | Properties of Big-O Notation | |

9.31.3. | Defining Big-Omega Notation | |

9.31.4. | Properties of Big-Omega Notation | |

9.31.5. | Defining Theta Notation | |

9.31.6. | Properties Theta Notation | |

9.31.7. | Time Complexity of Mathematical Procedures | |

9.31.8. | P vs. NP Problems |