## Table of Contents

- Part 1 – Fundamentals of Discrete Mathematics
- Fundamental Principles of Counting
- Fundamentals of Logic
- Basic Connectives and Truth Tables
- Logical Equivalence: The Laws of Logic
- Logical Implication: Rules of Inference
- The Use of Quantifiers
- Quantifiers, Definitions, and the Proofs of Theorems
- Summary and Historical Review

- Set Theory
- Sets and Subsets
- Set Operations and the Laws of Set Theory
- Counting and Venn Diagrams
- A Word on Probability
- Summary and Historical Review

- Properties of the Integers: Mathematical Induction
- Relations and Functions
- Cartesian Products and Relations
- Functions: Plain and One-to-One
- Onto Functions: Stirling Numbers of the Second Kind
- Special Functions
- The Pigeonhole Principle (lecture)
- Function Composition and Inverse Functions
- Computational Complexity
- Analysis of Algorithms
- Summary and Historical Review

- Languages: Finite State Machines
- Language: The Set Theory of Strings
- Finite State Machines: A First Encounter
- Finite State Machines: A Second Encounter
- Summary and Historical Review

- Relations: The Second Time Around
- Relations Revisited: Properties of Relations
- Computer Recognition: Zero-One Matrices and Directed Graphs
- Partial Orders: Hasse Diagrams
- Equivalence Relations and Partitions
- Finite State Machines: The Minimization Process
- Summary and Historical Review

- Part 2 – Further Topics In Enumeration
- The Principe of Inclusion and Exclusion
- Generating Functions
- Recurrence Relations
- The First-Order Linear Recurrence Relation (lecture)
- The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients
- The Nonhomogeneous Recurrence Relation
- The Method of Generating Functions (lecture)
- A Special Kind of Nonlinear Recurrence Relation (Optional)
- Divide-and-Conquer Algorithms (Optional)
- Summary and Historical Review

- Part 3 – Graph Theory and Applications
- An Introduction to Graph Theory
- Definitions and Examples
- Subgraphs, Complements and Graph Isomorphism
- Vertex Degree: Euler Trails and Circuits
- Planar Graphs
- Hamilton Paths and Cycles
- Graph Coloring and Chromatic Polynomials
- Summary and Historical Review

- Trees
- Definitions, Properties, and Examples
- Rooted Trees
- Tress and Sorting
- Weighted Trees and Prefix Codes
- Biconnected Components and Articulation Points
- Summary and Historical Review

- Optimization and Matching
- Dijkstra’s Shortest-Path Algorithm
- Minimal Spanning Trees: The Algorithms of Kruskal and Prim
- Transport Networks: The Max-Flow Min-Cut Theorem
- Matching Thoery
- Summary and Historical Review

- An Introduction to Graph Theory
- Part 4 – Modern Applied Algebra
- Rings and Modular Arithmetic
- The Ring Structure: Definition and Examples
- Ring Properties and Substructures
- The Integers Modulo n
- Ring Homomorphisms and Isomorphisms
- Summary and Historical Review

- Boolean Algebra and Switching Functions
- Switching Functions: Disjunctive and Conjunctive Normal Forms
- Gating Networks: Minimal Sums of Products: Karnaugh Maps
- Further Applications: Don’t Care Conditions
- The Structure of a Boolean Algebra (Optional)
- Summary and Historical Review

- Groups, Coding Theory, and Polya’s Method of Enumeration
- Definition, Examples, and Elementary Properties
- Homomorphisms, Isomorphisms, and Cyclic Groups
- Cosets and Lagrange’s Theorem
- Elements of Coding Theory
- The Hamming Metric
- The Parity-Check and Generator Matrices
- Group Codes: Decoding with Coset Leaders
- Hamming Matrices
- Counting and Equivalence: Burnside’s Theorem
- The Cycle Index
- The Pattern Inventory: Polya’s Method of Enumeration
- Summary and Historical Review

- Finite Fields and Combinatorial Designs
- Polynomial Rings
- Irreducible Polynomials: Finite Fields
- Latin Squares
- Finite Geometries and Affine Planes
- Block Designs and Projective Planes
- Summary and Historical Review

- Rings and Modular Arithmetic