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.
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.
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.1. Boolean Functions
Boolean Functions And Logical Operations
Disjunctive Normal Forms
Conjunctive Normal Forms
1.2. Classes of Boolean Functions
Truth-Preserving Boolean Functions
Falsity-Preserving Boolean Functions
Self-Dual Boolean Functions
Monotonic Boolean Functions
Affine Boolean Functions
Post's Functional Completeness Theorem
1.3. Logic Circuits
Introduction to Logic Circuits
Simplifying Logic Circuits
Logic Gates and Combinational Circuits
Simplifying Combinational Circuits
Simplifying Logical Expressions Using Karnaugh Maps
Simplifying Logical Expressions Using Quine-McCluskey Algorithm
2.4. Numbers in Different Bases
Adding and Subtracting Binary Integers
Multiplying and Dividing Binary Integers
Converting Between Binary and Hexadecimal
Integers in Arbitrary Bases
Floating Point Fractions in Arbitrary Bases
2.5. Fermat and Euler's Theorems
Fermat's Little Theorem
Euler's Totient Function
The Caesar Cipher
The Linear Cipher
Diffie-Hellman Shared Secret Exchange Protocol
Probability & Combinatorics
3.7. Discrete Random Variables
Probability Mass Functions of Discrete Random Variables
Cumulative Distribution Functions for Discrete Random Variables
Expected Values of Discrete Random Variables
The Binomial Distribution
Modeling With the Binomial Distribution
The Geometric Distribution
Modeling With the Geometric Distribution
The Discrete Uniform Distribution
Modeling With Discrete Uniform Distributions
The Poisson Distribution
Modeling With the Poisson Distribution
The Negative Binomial Distribution
Modeling With the Negative Binomial Distribution
3.8. Bayes' Theorem
Extending Bayes' Theorem
Permutations With Repetition
Applications of the Multinomial Theorem
K Permutations of N With Repetition
Combinations With Repetition
The Inclusion-Exclusion Principle
Counting Integer Solutions of a Constrained Equation
Applications of Combinatorics
Sequences & Recursion
4.10. Working With Geometric Series
Infinite Series and Partial Sums
Finding the Sum of an Infinite Geometric Series
Writing an Infinite Geometric Series in Sigma Notation
Finding the Sum of an Infinite Geometric Series Expressed in Sigma Notation
4.11. The Generalized Binomial Theorem
Introduction to the Generalized Binomial Theorem
Working With the Generalized Binomial Theorem
Determining the Range of Validity for a Generalized Binomial Expansion
Approximating Numerical Values Using the Generalized Binomial Theorem
4.12. The Multinomial Theorem
The Multinomial Theorem
Calculating the Number of Terms in a Multinomial Expansion
4.13. Recurrence Relations
Introduction to Recurrence Relations
First-Order Recurrence Relations
Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Distinct Real Roots
Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Repeated Roots
Second-Order Homogeneous Recurrence Relations: Characteristic Equations with Complex Roots
Second-Order Recurrence Relations with Polynomial Forcing
Second-Order Recurrence Relations with Exponential Forcing
4.14. Generating Functions
Generating Functions of Homogeneous Recurrence Relations
Determining the General Term of a Sequence Given Its Generating Function
Generating Functions for Inhomogeneous Recurrence Relations
Solving Recurrence Relations using Generating Functions
6.15. Introduction to Graph Theory
Introduction to Graphs
Edges and Vertices
The Degree of a Vertex
The Handshaking Lemma
6.16. Types of Graphs
Directed Acyclic Graphs
Complete Bipartite Graphs
6.17. Matrix Representations of Graphs
6.18. Connectivity in Graphs
Paths, Walks, and Trails
Cycles in Graphs
6.19. Graph Algorithms
Trees and Forests
Counting Spanning Trees
Minimum Spanning Trees
Algorithms on Graphs
7.21. Spanning Tree Algorithms
Applying Prim's Algorithm to a Distance Matrix
7.22. Shortest Path Algorithms
Shortest Paths in Unweighted Graphs
Shortest Paths in Weighted Graphs
The Bellman-Ford Algorithm
7.23. Eulerian Tours
The Chinese Postman Algorithm Applied to Eulerian Graphs
The Chinese Postman Algorithm Applied to Semi-Eulerian Graphs
7.24. Hamiltonian Graphs
Hamiltonian Cycles and Tours
The Traveling Salesperson Problem
Computing Upper Bounds for the Traveling Salesperson Problem
Computing Lower Bounds for the Traveling Salesperson Problem
The Nearest Neighbor Algorithm
7.25. Critical Path Analysis
Modeling a Project Using an Activity Network
Using Dummy Activities in Activity Networks
Applying Forward and Backward Passes to Activity Networks
Identifying Critical Activities in Activity Networks
Determining Floats in Activity Networks
Constructing Gantt Charts
Using Gantt Charts to Solve Problems
Matchings in Bipartite Graphs
The Maximum Matching Algorithm
Matchings in General Graphs
7.27. Network Flows
Introduction to Network Flows
Cuts in Networks
Finding Initial Flows Through Networks
Increasing Flows Through Networks
The Maximum-Flow Minimum-Cut Theorem
Increasing Flows Through Networks With Multiple Sources/Sinks