Discrete MathematicsDiscrete Mathematics

Propositions and connectives, implications and their contrapositives, logical equivalence and De Morgan's laws, quantifiers, and Boolean algebra with logic gates.

1. 1Statements and Connectives
2. 2Implications, Converses and Contrapositives
3. 3Logical Equivalence and De Morgan's Laws
4. 4Predicates and Quantifiers
5. 5Boolean Algebra and Logic Gates

Direct proof and proof by contrapositive, proof by contradiction, mathematical induction, and strong induction.

1. 6Direct Proof and Proof by Contrapositive
2. 7Proof by Contradiction
3. 8Mathematical Induction
4. 9Strong Induction and Well-Ordering

Sets and their operations, one-to-one and onto functions, equivalence relations, and partial orders with Hasse diagrams.

1. 10Sets and Set Operations
2. 11Functions: One-to-One and Onto
3. 12Relations and Equivalence Relations
4. 13Partial Orders and Hasse Diagrams

The sum and product rules, permutations and combinations, the binomial theorem, counting multisets, inclusion–exclusion and the pigeonhole principle.

1. 14The Sum and Product Rules
2. 15Permutations and Combinations
3. 16The Binomial Theorem and Pascal's Triangle
4. 17Counting Multisets: Stars and Bars
5. 18Inclusion–Exclusion
6. 19The Pigeonhole Principle

Arithmetic and geometric sequences and their sums, recurrence relations, solving linear recurrences with characteristic roots, and generating functions.

1. 20Sequences, Sums and Closed Forms
2. 21Recurrence Relations
3. 22Solving Linear Recurrences
4. 23Generating Functions

Divisibility and primes, the Euclidean algorithm, modular arithmetic, modular inverses and the Chinese remainder theorem, and RSA encryption.

1. 24Divisibility and Prime Numbers
2. 25The GCD and the Euclidean Algorithm
3. 26Modular Arithmetic
4. 27Modular Inverses and the Chinese Remainder Theorem
5. 28Public-Key Cryptography: RSA

Binary and hexadecimal, two's complement, bitwise operations and masks, fixed and floating point, error-detecting and error-correcting codes, state machines, and turning signals into bits: the discrete math that firmware and hardware run on.

1. 29Binary and Hexadecimal
2. 30Negative Numbers: Two's Complement
3. 31Bitwise Operations and Masks
4. 32Fractions in Binary: Fixed and Floating Point
5. 33Error Detection: Parity, Checksums and CRCs
6. 34Error-Correcting Codes: Hamming Codes
7. 35Finite State Machines
8. 36From Signals to Bits: Sampling and Quantization

Graphs and degrees, paths and shortest paths, Euler and Hamilton paths, trees and spanning trees, planar graphs and coloring, and bipartite matching.

1. 37Graphs, Degrees and the Handshake Lemma
2. 38Paths, Connectivity and Shortest Paths
3. 39Euler and Hamilton Paths
4. 40Trees and Spanning Trees
5. 41Planar Graphs and Coloring
6. 42Bipartite Graphs and Matching

Growth rates and big-O notation, and analyzing searching and sorting algorithms with recurrences.

1. 43Growth of Functions and Big-O
2. 44Analyzing Algorithms: Searching and Sorting