Math Academy

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

Logic

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.

Number Theory

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.

Probability & Combinatorics

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.

Sequences & Recursion

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.

Graph Theory

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.

Graph Algorithms

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.

General Algorithms

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.

Preliminaries

3 topics

1.1. Sets

	1.1.1.	Partial Order
	1.1.2.	Properties of Elements in Posets
	1.1.3.	The Pigeonhole Principle

Boolean Algebra

18 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.	Principal Disjunctive Normal Forms
	2.2.5.	Conjunctive Normal Forms
	2.2.6.	Principal Conjunctive Normal Forms
	2.2.7.	Boolean Polynomials

2.3. Classes of Boolean Functions

	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. 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 Logical Expressions Using Karnaugh Maps
	2.4.5.	Simplifying Logical Expressions Using Quine-McCluskey Algorithm

Number Theory

15 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

Probability & Combinatorics

30 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.9. The Discrete Uniform Distribution

	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. The Bernoulli Distribution

	4.10.1.	The Bernoulli Distribution
	4.10.2.	Mean and Variance of the Bernoulli Distribution

4.11. The Binomial Distribution

	4.11.1.	The Binomial Distribution
	4.11.2.	Modeling With the Binomial Distribution

4.12. The Poisson Distribution

	4.12.1.	The Poisson Distribution
	4.12.2.	Modeling With the Poisson Distribution

4.13. The Geometric Distribution

	4.13.1.	The Geometric Distribution
	4.13.2.	Modeling With the Geometric Distribution

4.14. The Negative Binomial Distribution

	4.14.1.	The Negative Binomial Distribution
	4.14.2.	Modeling With the Negative Binomial Distribution

4.15. The Hypergeometric Distribution

	4.15.1.	The Hypergeometric Distribution
	4.15.2.	The PMF of the Hypergeometric Distribution
	4.15.3.	Modeling With the Hypergeometric Distribution

4.16. Bayes' Theorem

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

	4.17.1.	Permutations With Repetition
	4.17.2.	Applications of the Multinomial Theorem
	4.17.3.	K Permutations of N With Repetition
	4.17.4.	Combinations With Repetition
	4.17.5.	The Inclusion-Exclusion Principle
	4.17.6.	Counting Integer Solutions of a Constrained Equation
	4.17.7.	Partitions

Sequences & Recursion

26 topics

5.18. Working With Geometric Series

	5.18.1.	Infinite Series and Partial Sums
	5.18.2.	Finding the Sum of an Infinite Geometric Series
	5.18.3.	Writing an Infinite Geometric Series in Sigma Notation
	5.18.4.	Sums of Infinite Geometric Series Given in Sigma Notation

5.19. The Generalized Binomial Theorem

	5.19.1.	Introduction to the Generalized Binomial Theorem
	5.19.2.	Working With the Generalized Binomial Theorem
	5.19.3.	Determining the Range of Validity for a Generalized Binomial Expansion
	5.19.4.	Approximating Numerical Values Using the Generalized Binomial Theorem

5.20. The Multinomial Theorem

	5.20.1.	The Multinomial Theorem
	5.20.2.	Calculating the Number of Terms in a Multinomial Expansion

5.21. Recurrence Relations

	5.21.1.	Introduction to Recurrence Relations
	5.21.2.	First-Order Recurrence Relations
	5.21.3.	First-Order Recurrence Relations With Polynomial Forcing
	5.21.4.	First-Order Recurrence Relations With Exponential Forcing
	5.21.5.	First-Order Recurrence Relations With Mixed Forcing
	5.21.6.	Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Distinct Real Roots
	5.21.7.	Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Repeated Roots
	5.21.8.	Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Complex Roots
	5.21.9.	Second-Order Recurrence Relations with Polynomial Forcing
	5.21.10.	Second-Order Recurrence Relations with Exponential Forcing

5.22. Generating Functions

	5.22.1.	Generating Functions
	5.22.2.	Generating Functions of Homogeneous Recurrence Relations
	5.22.3.	Determining the General Term of a Sequence Given Its Generating Function
	5.22.4.	Generating Functions for Inhomogeneous Recurrence Relations
	5.22.5.	Solving Homogeneous Recurrence Relations Using Generating Functions
	5.22.6.	Solving Inhomogeneous Recurrence Relations Using Generating Functions

Graph Theory

22 topics

6.23. Introduction to Graph Theory

	6.23.1.	Introduction to Graphs
	6.23.2.	Walks, Paths, and Distances
	6.23.3.	Walks, Paths, and Distances in Directed Graphs
	6.23.4.	The Degree of a Vertex
	6.23.5.	The Handshaking Lemma
	6.23.6.	Subgraphs

6.24. Connectivity in Graphs

	6.24.1.	Cycles in Graphs
	6.24.2.	Connected Graphs
	6.24.3.	Cut Vertices and Cut Edges

6.25. Types of Graphs

	6.25.1.	Directed Acyclic Graphs
	6.25.2.	Regular Graphs
	6.25.3.	Platonic Graphs
	6.25.4.	Planar Graphs

6.26. Matrix Representations of Graphs

	6.26.1.	Incidence Matrices
	6.26.2.	Adjacency Matrices
	6.26.3.	Adjacency Matrices of Directed Graphs
	6.26.4.	Distance Matrices

6.27. Trees

	6.27.1.	Trees and Forests
	6.27.2.	Counting Trees
	6.27.3.	Spanning Trees
	6.27.4.	Counting Spanning Trees
	6.27.5.	Minimum Spanning Trees

Algorithms on Graphs

23 topics

7.28. Search Algorithms

	7.28.1.	Breadth-First Search
	7.28.2.	Depth-First Search
	7.28.3.	Kahn's Algorithm

7.29. Spanning Tree Algorithms

	7.29.1.	Kruskal's Algorithm
	7.29.2.	Prim's Algorithm
	7.29.3.	Applying Prim's Algorithm to a Distance Matrix

7.30. Shortest Path Algorithms

	7.30.1.	Shortest Paths in Unweighted Graphs
	7.30.2.	Shortest Paths in Weighted Graphs
	7.30.3.	The Bellman-Ford Algorithm
	7.30.4.	Dijkstra's Algorithm
	7.30.5.	A* Search

7.31. Eulerian Tours

	7.31.1.	Eulerian Graphs
	7.31.2.	Fleury's Algorithm
	7.31.3.	The Chinese Postman Algorithm Applied to Eulerian Graphs
	7.31.4.	The Chinese Postman Algorithm Applied to Semi-Eulerian Graphs

7.32. Hamiltonian Graphs

	7.32.1.	Hamiltonian Cycles and Tours
	7.32.2.	The Traveling Salesperson Problem
	7.32.3.	Computing Upper Bounds for the Traveling Salesperson Problem
	7.32.4.	Computing Lower Bounds for the Traveling Salesperson Problem
	7.32.5.	The Nearest Neighbor Algorithm

7.33. Matchings

	7.33.1.	Matchings in Bipartite Graphs
	7.33.2.	The Maximum Matching Algorithm
	7.33.3.	Matchings in General Graphs

The Theory of Algorithms

14 topics

8.34. Finite-State Transducers

	8.34.1.	Mealy Machines
	8.34.2.	Moore Machines

8.35. Finite-State Interceptors

	8.35.1.	Deterministic Finite Automata
	8.35.2.	Extending the Transition Function of a DFA to Strings
	8.35.3.	Nondeterministic Finite Automata
	8.35.4.	The Language of Automata
	8.35.5.	Regular Expressions
	8.35.6.	Context-Free Grammars
	8.35.7.	Introduction to Turing Machines
	8.35.8.	Working With Turing Machines
	8.35.9.	Nondeterministic Turing Machines

8.36. Algorithmic Complexity

	8.36.1.	Defining Big-O Notation
	8.36.2.	Defining Big-Omega Notation
	8.36.3.	Defining Theta Notation

Discrete Mathematics

Overview

Outcomes

Content

Logic

Number Theory

Probability & Combinatorics

Sequences & Recursion

Graph Theory

Graph Algorithms

General Algorithms