Master Outline

Discrete Mathematics for Computer Science — The Mathematical Foundations of Computing

This outline is the section-level map of the entire book: 40 chapters across 6 parts. For each chapter it lists difficulty, estimated time, hard prerequisites (by chapter number), learning objectives, the section breakdown, key terms first introduced, and the chapter's role in the book's two long threads — the anchor examples (RSA, social-network graphs, Fibonacci) and the Discrete Math Toolkit project.

How to read this outline

Difficulty sets the concept budget per the learning-science backbone: beginner (3–5 new concepts, 8–12 new terms, 1–2 techniques), intermediate (5–8 / 12–18 / 2–4), advanced (6–10 / 15–25 / 3–5). Authors compress to fit the budget; they do not pad.
Prereqs are hard dependencies (the reader must have read them). Soft connections are made via cross-references inside chapters.
Every chapter opens with a CS hook ("why a programmer needs this"), reaches a worked proof with its strategy stated first, includes Python that is shown with expected output (never run), and ends with a Project Checkpoint that extends the Toolkit.

Part I — Logic and Proof

The grammar of mathematics and the skill that defines the book: writing and reading proofs. We start with the logic that underlies every if statement and circuit, then build the proof techniques used throughout the rest of the book.

Chapter 1: Propositional Logic

Difficulty: beginner · Time: 5–6 h · Prereqs: none
Objectives: translate English statements into propositional logic; build and read truth tables; identify tautologies, contradictions, and logical equivalences; connect logical connectives to Boolean operators in code.
Sections: 1.1 Why logic? (bugs, conditions, and circuits) · 1.2 Propositions and connectives (¬, ∧, ∨, →, ↔, ⊕) · 1.3 Truth tables · 1.4 Logical equivalences and De Morgan's laws · 1.5 Simplifying conditions (the programmer's payoff) · 1.6 SAT: the first hard problem (preview) · Summary, Project Checkpoint.
Key terms: proposition, connective, truth table, tautology, contradiction, logical equivalence, De Morgan's laws, satisfiability.
Threads: Toolkit → start logic.py (a truth-table generator). CS hook → simplifying if conditions; short-circuit evaluation.

Chapter 2: Predicate Logic and Quantifiers

Difficulty: beginner · Time: 5–6 h · Prereqs: 1
Objectives: use predicates and the quantifiers ∀, ∃; negate quantified statements; translate multiply-quantified statements; relate quantifiers to loops and assertions.
Sections: 2.1 From propositions to predicates · 2.2 Universal and existential quantifiers · 2.3 Nested quantifiers and order · 2.4 Negation (pushing ¬ through quantifiers) · 2.5 Quantifiers as loops and all()/any() · 2.6 Specifying programs: preconditions and postconditions · Summary, Project Checkpoint.
Key terms: predicate, domain, universal/existential quantifier, bound/free variable, nested quantifier, counterexample.
Threads: Toolkit → extend logic.py with a predicate evaluator over finite domains.

Chapter 3: Rules of Inference

Difficulty: intermediate · Time: 6 h · Prereqs: 1, 2
Objectives: apply valid inference rules (modus ponens, modus tollens, etc.); distinguish valid arguments from fallacies; construct formal derivations; recognize inference in type systems.
Sections: 3.1 Arguments and validity · 3.2 Inference rules for propositions · 3.3 Common fallacies (affirming the consequent, etc.) · 3.4 Inference with quantifiers (instantiation, generalization) · 3.5 Building a derivation step by step · 3.6 Where inference lives in CS (type checking, logic programming) · Summary, Project Checkpoint.
Key terms: argument, premise, conclusion, validity, soundness, modus ponens/tollens, fallacy, derivation.
Threads: sets up the proof chapters; CS hook → type inference / Prolog.

Chapter 4: Proof Strategies I — Direct Proof and Contraposition

Difficulty: intermediate · Time: 6–7 h · Prereqs: 1, 2, 3
Objectives: write a rigorous direct proof; use definitions precisely; prove by contraposition; structure a proof for a reader.
Sections: 4.1 What a proof is (and isn't) · 4.2 Definitions as the raw material · 4.3 Direct proof (even/odd, divisibility) · 4.4 Proof by contraposition · 4.5 Proof template and common mistakes · 4.6 Reading proofs critically · Summary, Project Checkpoint.
Key terms: theorem, lemma, corollary, conjecture, direct proof, contrapositive, vacuous/trivial proof.
Threads: anchor → first appearance of divisibility (sets up number theory). CS hook → proving a function's contract holds.

Chapter 5: Proof Strategies II — Contradiction and Cases

Difficulty: intermediate · Time: 6–7 h · Prereqs: 4
Objectives: prove by contradiction; prove by exhaustive cases; prove existence and uniqueness; recognize when each strategy fits.
Sections: 5.1 Proof by contradiction (√2 irrational, infinitude of primes) · 5.2 Contradiction in CS: unsolvability previews · 5.3 Proof by cases · 5.4 Existence and uniqueness proofs · 5.5 Counterexamples and disproof · 5.6 Choosing a strategy · Summary, Project Checkpoint.
Key terms: proof by contradiction, proof by cases, existence/uniqueness proof, without loss of generality, counterexample.
Threads: CS hook → contradiction is how you prove the halting problem is unsolvable (forward ref to Ch. 36).

Chapter 6: Mathematical Induction (sample chapter / voice anchor)

Difficulty: intermediate · Time: 7 h · Prereqs: 4, 5
Objectives: write a proof by mathematical induction; identify base case and inductive step; connect induction to recursion and loop invariants; prove a recursive program correct.
Sections: 6.1 The intuition: dominoes and recursion · 6.2 The principle of induction · 6.3 Worked inductions (sums, inequalities, divisibility) · 6.4 Induction ↔ recursion (Fibonacci) · 6.5 Loop invariants: induction for iterative code · 6.6 Find-the-error: flawed inductions · Summary, Project Checkpoint.
Key terms: induction, base case, inductive step, inductive hypothesis, loop invariant.
Threads: anchor → Fibonacci introduced and proven about. CS hook → proving loops correct. Threshold concept: induction.

Chapter 7: Strong Induction, Well-Ordering, and Recursive Definitions

Difficulty: advanced · Time: 7 h · Prereqs: 6
Objectives: use strong induction; apply the well-ordering principle; write recursive definitions; use structural induction on recursively defined objects.
Sections: 7.1 Strong induction (and when you need it) · 7.2 Well-ordering principle · 7.3 Recursive definitions (sequences, sets, structures) · 7.4 Structural induction · 7.5 Recursion in data structures (trees, lists) · 7.6 Equivalence of induction forms · Summary, Project Checkpoint.
Key terms: strong induction, well-ordering, recursive definition, structural induction, recursively defined set.
Threads: anchor → Fibonacci via strong induction; sets up recurrences (Ch. 18–19) and trees (Ch. 31).

Part II — Structures

The fundamental objects of discrete math — sets, functions, relations — and the structures built from them. These are the data types of mathematics, and they map directly onto the data structures of programming.

Chapter 8: Sets

Difficulty: beginner · Time: 5–6 h · Prereqs: 1, 2
Objectives: use set notation and operations; prove set identities; compute power sets and Cartesian products; use Python sets fluently.
Sections: 8.1 Sets and membership · 8.2 Subsets, equality, power sets · 8.3 Set operations (∪, ∩, −, complement) and Venn diagrams · 8.4 Cartesian products · 8.5 Proving set identities · 8.6 Sets in code (set, frozenset, sets vs. lists) · Summary, Project Checkpoint.
Key terms: set, element, subset, power set, union, intersection, complement, Cartesian product, cardinality (finite).
Threads: Toolkit → sets.py (set ops from scratch over a universe). CS hook → deduplication, membership testing, hash sets.

Chapter 9: Functions

Difficulty: intermediate · Time: 6 h · Prereqs: 8
Objectives: define functions formally; classify as injective/surjective/bijective; compose and invert functions; connect to hashing and type signatures.
Sections: 9.1 Functions as relations with a rule · 9.2 Domain, codomain, range · 9.3 Injective, surjective, bijective · 9.4 Composition and inverses · 9.5 Important functions (floor, ceiling, mod, exponential, log) · 9.6 Functions in CS (hash functions, pure functions, type signatures) · Summary, Project Checkpoint.
Key terms: function, injection, surjection, bijection, composition, inverse, image/preimage, floor/ceiling.
Threads: sets up cardinality (Ch. 10) via bijections; CS hook → hashing (forward ref Ch. 26).

Chapter 10: Cardinality and Infinity (added)

Difficulty: advanced · Time: 6–7 h · Prereqs: 9
Objectives: compare set sizes via bijections; distinguish countable from uncountable; run Cantor's diagonal argument; draw the consequence that uncomputable problems exist.
Sections: 10.1 Sizing sets by matching (bijections) · 10.2 Countable sets (ℤ, ℚ) · 10.3 Cantor's diagonalization: ℝ is uncountable · 10.4 There are more problems than programs · 10.5 The hierarchy of infinities (brief) · 10.6 Why a programmer should care (limits of computation) · Summary, Project Checkpoint.
Key terms: cardinality, countable, uncountable, bijection, diagonalization, aleph-null.
Threads: CS hook → sets up computability (Ch. 36) directly. Threshold concept: uncountability.

Chapter 11: Sequences and Summations

Difficulty: intermediate · Time: 5–6 h · Prereqs: 6, 9
Objectives: work with sequences and summation notation; evaluate arithmetic/geometric series; manipulate sums; estimate growth.
Sections: 11.1 Sequences (closed-form vs. recursive) · 11.2 Summation notation and properties · 11.3 Arithmetic and geometric series · 11.4 Useful closed forms and telescoping · 11.5 Products and factorials · 11.6 Sums in algorithm analysis (the cost of nested loops) · Summary, Project Checkpoint.
Key terms: sequence, series, summation, arithmetic/geometric series, telescoping, factorial.
Threads: anchor → Fibonacci as a sequence; sets up complexity (Ch. 14) and recurrences (Ch. 18).

Chapter 12: Relations

Difficulty: intermediate · Time: 6–7 h · Prereqs: 8, 9
Objectives: represent relations; classify properties (reflexive, symmetric, transitive); build equivalence relations and partitions; compute closures.
Sections: 12.1 Relations as sets of pairs · 12.2 Representing relations (matrix, digraph) · 12.3 Properties of relations · 12.4 Equivalence relations and partitions · 12.5 Closures (transitive closure) · 12.6 Relations in databases (the relational model) · Summary, Project Checkpoint.
Key terms: relation, reflexive/symmetric/antisymmetric/transitive, equivalence relation, equivalence class, partition, transitive closure.
Threads: CS hook → relational databases; sets up partial orders (Ch. 13) and graphs (Ch. 27).

Chapter 13: Partial Orders, Lattices, and Boolean Algebra

Difficulty: advanced · Time: 7 h · Prereqs: 12
Objectives: work with partial orders and Hasse diagrams; identify lattices; topologically sort; connect Boolean algebra to logic and circuits.
Sections: 13.1 Partial orders and Hasse diagrams · 13.2 Total orders, chains, antichains · 13.3 Topological sort (and build systems) · 13.4 Lattices, lub/glb · 13.5 Boolean algebra and its laws · 13.6 From Boolean algebra to logic gates · Summary, Project Checkpoint.
Key terms: partial order, poset, Hasse diagram, total order, lattice, join/meet, Boolean algebra, topological sort.
Threads: CS hook → dependency resolution / make; ties back to logic (Ch. 1).

Chapter 14: Algorithms and Complexity

Difficulty: intermediate · Time: 7 h · Prereqs: 9, 11
Objectives: define algorithms precisely; analyze running time; use Big-O, Big-Ω, Big-Θ; compare growth rates; reason about worst/average case.
Sections: 14.1 What is an algorithm? · 14.2 Measuring work (the RAM model) · 14.3 Big-O, Big-Ω, Big-Θ formally · 14.4 Analyzing loops and common patterns · 14.5 Growth-rate hierarchy and why it dominates · 14.6 Best/worst/average case; a first lower bound · Summary, Project Checkpoint.
Key terms: algorithm, Big-O/Ω/Θ, asymptotic, polynomial/exponential time, worst/average case.
Threads: the analytical spine for the rest of the book; sets up recurrences (Ch. 19), graph algorithms (Part V), complexity theory (Ch. 37).

Part III — Counting and Probability

How to count without listing, and how to reason about uncertainty. Combinatorics and probability are the foundations of algorithm analysis, cryptography, hashing, and machine learning.

Chapter 15: The Basics of Counting

Difficulty: beginner · Time: 5–6 h · Prereqs: 8
Objectives: apply the product and sum rules; use the subtraction (inclusion–exclusion for two sets) and division rules; count with constraints; count program states.
Sections: 15.1 Why count? (passwords, test cases, states) · 15.2 The product rule · 15.3 The sum rule · 15.4 Inclusion–exclusion (two and three sets) · 15.5 The division rule · 15.6 Counting the size of an input space · Summary, Project Checkpoint.
Key terms: product rule, sum rule, inclusion–exclusion, division rule, counting principle.
Threads: Toolkit → begin combinatorics.py; CS hook → password/keyspace sizing (ties to crypto).

Chapter 16: Permutations and Combinations

Difficulty: intermediate · Time: 6–7 h · Prereqs: 15
Objectives: count permutations and combinations; use binomial coefficients; apply the binomial theorem; count with/without repetition.
Sections: 16.1 Permutations · 16.2 Combinations and $\binom{n}{k}$ · 16.3 Permutations vs. combinations (choosing the model) · 16.4 The binomial theorem and Pascal's triangle · 16.5 Combinatorial proofs · 16.6 Counting in algorithms (subsets, search spaces) · Summary, Project Checkpoint.
Key terms: permutation, combination, binomial coefficient, binomial theorem, Pascal's triangle, combinatorial proof.
Threads: Toolkit → permutation/combination generators; CS hook → brute-force search sizes.

Chapter 17: Advanced Counting

Difficulty: advanced · Time: 7 h · Prereqs: 16
Objectives: apply the pigeonhole principle; count with stars and bars; use generating functions as a counting tool; apply inclusion–exclusion in general.
Sections: 17.1 The pigeonhole principle (and hashing collisions) · 17.2 Generalized pigeonhole · 17.3 Stars and bars (counting distributions) · 17.4 General inclusion–exclusion · 17.5 Generating functions: counting with algebra · 17.6 Applications (derangements, surjection counts) · Summary, Project Checkpoint.
Key terms: pigeonhole principle, stars and bars, generating function, derangement, inclusion–exclusion (general).
Threads: CS hook → why hash collisions are unavoidable (ties to Ch. 26).

Chapter 18: Recurrence Relations

Difficulty: intermediate · Time: 6–7 h · Prereqs: 7, 11
Objectives: model problems with recurrences; classify them; solve linear homogeneous recurrences; recognize recurrences from recursive code.
Sections: 18.1 What is a recurrence? · 18.2 Modeling with recurrences (Tower of Hanoi, tilings) · 18.3 Linear homogeneous recurrences · 18.4 The characteristic equation · 18.5 Nonhomogeneous recurrences (intro) · 18.6 From recursive code to recurrence · Summary, Project Checkpoint.
Key terms: recurrence relation, initial condition, linear homogeneous recurrence, characteristic equation.
Threads: anchor → Fibonacci recurrence and its closed form (golden ratio).

Chapter 19: Solving Recurrence Relations

Difficulty: advanced · Time: 7 h · Prereqs: 14, 18
Objectives: solve divide-and-conquer recurrences; apply the Master Theorem; analyze merge sort and binary search; compute Fibonacci efficiently.
Sections: 19.1 Divide-and-conquer recurrences · 19.2 The recursion tree method · 19.3 The Master Theorem · 19.4 Merge sort and binary search analyzed · 19.5 Fibonacci: matrix exponentiation in $O(\log n)$ · 19.6 When the Master Theorem fails · Summary, Project Checkpoint.
Key terms: divide-and-conquer, recursion tree, Master Theorem, matrix exponentiation.
Threads: anchor → Fibonacci computed in log time; ties to complexity (Ch. 14) and sorting.

Chapter 20: Discrete Probability

Difficulty: intermediate · Time: 6–7 h · Prereqs: 16
Objectives: build probability spaces; compute event probabilities; use random variables and expected value; apply the probabilistic method; verify with simulation.
Sections: 20.1 Sample spaces and events · 20.2 Probability axioms · 20.3 Random variables · 20.4 Expected value and linearity · 20.5 Variance (intro) · 20.6 The probabilistic method; simulation vs. proof · Summary, Project Checkpoint.
Key terms: sample space, event, random variable, expected value, linearity of expectation, variance, probabilistic method.
Threads: Toolkit → probability.py (Monte-Carlo simulators); theme → computation tests, proof guarantees.

Chapter 21: Conditional Probability and Bayes' Theorem (added)

Difficulty: advanced · Time: 6–7 h · Prereqs: 20
Objectives: compute conditional probabilities; apply Bayes' theorem; reason about independence; analyze a randomized algorithm and a naive Bayes classifier.
Sections: 21.1 Conditional probability · 21.2 Independence · 21.3 Bayes' theorem · 21.4 The base rate fallacy (medical tests, spam) · 21.5 Naive Bayes classification · 21.6 Randomized algorithms (and why they work) · Summary, Project Checkpoint.
Key terms: conditional probability, independence, Bayes' theorem, prior/posterior, base rate, naive Bayes.
Threads: CS hook → spam filtering, randomized algorithms (e.g., quicksort pivoting).

Part IV — Number Theory and Cryptography

The "useless" branch of math that turned out to secure the entire internet. We build from divisibility to a working RSA implementation, then to the hashing and error detection in every data transfer.

Chapter 22: Number Theory Foundations

Difficulty: intermediate · Time: 6–7 h · Prereqs: 4, 5, 6
Objectives: reason about divisibility; compute gcd via the Euclidean algorithm; use Bézout's identity; apply the Fundamental Theorem of Arithmetic.
Sections: 22.1 Divisibility · 22.2 Primes and the sieve of Eratosthenes · 22.3 The division algorithm · 22.4 GCD and the Euclidean algorithm · 22.5 Bézout's identity and the extended Euclidean algorithm · 22.6 The Fundamental Theorem of Arithmetic · Summary, Project Checkpoint.
Key terms: divisibility, prime, composite, gcd, Euclidean algorithm, Bézout's identity, FTA.
Threads: anchor → RSA groundwork begins; Toolkit → numbertheory.py (gcd, sieve).

Chapter 23: Modular Arithmetic

Difficulty: intermediate · Time: 6–7 h · Prereqs: 22
Objectives: compute in modular arithmetic; solve linear congruences; find modular inverses; apply the Chinese Remainder Theorem; do fast modular exponentiation.
Sections: 23.1 Congruence mod n · 23.2 Modular arithmetic rules · 23.3 Linear congruences and modular inverses · 23.4 The Chinese Remainder Theorem · 23.5 Fast modular exponentiation · 23.6 Fermat's little theorem and Euler's theorem · Summary, Project Checkpoint.
Key terms: congruence, residue, modular inverse, CRT, modular exponentiation, Fermat/Euler theorem, totient.
Threads: anchor → the engine of RSA; Toolkit → modular inverse, fast pow.

Chapter 24: Algebraic Structures — Groups, Rings, and Fields (added)

Difficulty: advanced · Time: 7 h · Prereqs: 23
Objectives: define groups, rings, fields; verify the axioms; work in $\mathbb{Z}_n$ and finite fields; see why structure powers crypto and coding theory.
Sections: 24.1 What is an algebraic structure? · 24.2 Groups and their properties · 24.3 Cyclic groups and generators · 24.4 Rings and fields · 24.5 Finite fields $\mathrm{GF}(p)$ and $\mathrm{GF}(2^n)$ · 24.6 Why CS cares (crypto, coding, hashing) · Summary, Project Checkpoint.
Key terms: group, abelian, subgroup, cyclic group, generator, ring, field, finite field.
Threads: anchor → the abstract "why" behind RSA's correctness; sets up coding theory (Ch. 38).

Chapter 25: Cryptography — From Caesar Cipher to RSA

Difficulty: advanced · Time: 7–8 h · Prereqs: 23, 24
Objectives: analyze classical ciphers; explain symmetric vs. public-key crypto; implement RSA; explain RSA's security in terms of computational hardness.
Sections: 25.1 Classical ciphers and why they fail · 25.2 The key-exchange problem · 25.3 Public-key cryptography (the idea) · 25.4 RSA: key generation, encryption, decryption · 25.5 Why RSA works (a proof via Euler) · 25.6 Why RSA is secure (factoring hardness); pitfalls · Summary, Project Checkpoint.
Key terms: cipher, symmetric/public-key crypto, RSA, trapdoor function, key generation, digital signature (intro).
Threads: anchor → RSA payoff — reader implements RSA; sets up the capstone option A.

Chapter 26: Hashing, Checksums, and Error Detection

Difficulty: intermediate · Time: 6 h · Prereqs: 23
Objectives: design and analyze hash functions; reason about collisions; compute checksums and CRCs; distinguish detection from correction.
Sections: 26.1 Hash functions and hash tables · 26.2 Collisions and the pigeonhole principle · 26.3 Modular hashing and universal hashing (intro) · 26.4 Checksums and parity · 26.5 Cyclic redundancy checks (CRC) · 26.6 Cryptographic hashing (intro) · Summary, Project Checkpoint.
Key terms: hash function, collision, load factor, checksum, parity bit, CRC, cryptographic hash.
Threads: ties pigeonhole (Ch. 17) + modular arithmetic; sets up coding theory (Ch. 38).

Part V — Graph Theory

The most useful structure in computer science. We model everything from social networks to road maps to dependencies as graphs, then develop the algorithms that make them computable.

Chapter 27: Introduction to Graphs

Difficulty: beginner · Time: 6 h · Prereqs: 8, 12
Objectives: use graph terminology; classify graph types; apply the handshaking lemma; model real problems as graphs.
Sections: 27.1 What is a graph? · 27.2 Terminology (degree, path, cycle, connected) · 27.3 Types of graphs (directed, weighted, bipartite, complete) · 27.4 The handshaking lemma · 27.5 Graph isomorphism (intro) · 27.6 Modeling with graphs (social networks, maps, the web) · Summary, Project Checkpoint.
Key terms: graph, vertex, edge, degree, path, cycle, connected, directed/weighted/bipartite, handshaking lemma.
Threads: anchor → social-network graphs introduced; Toolkit → graphs.py begins.

Chapter 28: Graph Representations, Traversal, and Search

Difficulty: intermediate · Time: 7 h · Prereqs: 27, 14
Objectives: represent graphs (matrix vs. list); implement BFS and DFS; use traversal to test connectivity and find paths; analyze traversal complexity.
Sections: 28.1 Adjacency matrix vs. adjacency list · 28.2 Breadth-first search · 28.3 Depth-first search · 28.4 Applications (connectivity, cycle detection, components) · 28.5 Topological sort via DFS · 28.6 Complexity of traversal · Summary, Project Checkpoint.
Key terms: adjacency matrix/list, BFS, DFS, connected component, spanning tree (intro).
Threads: anchor → BFS for "degrees of separation" in a social network.

Chapter 29: Weighted Graphs and Shortest Paths (added)

Difficulty: intermediate · Time: 7 h · Prereqs: 28
Objectives: model weighted graphs; implement Dijkstra's algorithm; handle negative weights with Bellman–Ford; reason about correctness.
Sections: 29.1 Weighted graphs and shortest-path problems · 29.2 Dijkstra's algorithm · 29.3 Why Dijkstra is correct (greedy + invariant) · 29.4 Bellman–Ford and negative edges · 29.5 All-pairs shortest paths (Floyd–Warshall, intro) · 29.6 Routing in the real world (GPS, networks) · Summary, Project Checkpoint.
Key terms: weighted graph, shortest path, Dijkstra, priority queue, Bellman–Ford, relaxation.
Threads: CS hook → GPS / packet routing; greedy-correctness proof.

Chapter 30: Euler Paths, Hamilton Paths, and the TSP

Difficulty: advanced · Time: 6–7 h · Prereqs: 27, 28
Objectives: characterize Euler paths/circuits; contrast Hamilton paths; state the TSP; recognize the easy/hard boundary.
Sections: 30.1 The bridges of Königsberg · 30.2 Euler paths and circuits (and the theorem) · 30.3 Hamilton paths and circuits · 30.4 Why Hamilton is hard but Euler is easy · 30.5 The Traveling Salesman Problem · 30.6 Heuristics for hard problems · Summary, Project Checkpoint.
Key terms: Euler path/circuit, Hamilton path/circuit, TSP, NP-hard (preview), heuristic.
Threads: sets up complexity theory (Ch. 37); the easy-vs-hard boundary.

Chapter 31: Trees

Difficulty: intermediate · Time: 7 h · Prereqs: 27, 7
Objectives: characterize trees; use rooted/binary trees; traverse trees; apply trees in CS (BSTs, heaps, parsing, Huffman).
Sections: 31.1 Trees and their properties (n−1 edges) · 31.2 Rooted trees and terminology · 31.3 Binary trees and traversals · 31.4 Binary search trees · 31.5 Tree applications (heaps, expression trees, tries) · 31.6 Huffman coding · Summary, Project Checkpoint.
Key terms: tree, forest, rooted tree, binary tree, BST, traversal (pre/in/post-order), Huffman coding.
Threads: structural induction (Ch. 7) pays off; Huffman ties to coding theory (Ch. 38).

Chapter 32: Spanning Trees and Minimum Spanning Trees

Difficulty: intermediate · Time: 6–7 h · Prereqs: 31, 29
Objectives: find spanning trees; compute MSTs with Kruskal and Prim; justify greedy correctness; use union-find.
Sections: 32.1 Spanning trees · 32.2 The MST problem · 32.3 Kruskal's algorithm and union-find · 32.4 Prim's algorithm · 32.5 Why the greedy MST algorithms are correct (cut property) · 32.6 Network design applications · Summary, Project Checkpoint.
Key terms: spanning tree, MST, Kruskal, Prim, union-find, cut property, greedy algorithm.
Threads: CS hook → network/infrastructure design; greedy proofs.

Chapter 33: Graph Coloring and Planarity

Difficulty: advanced · Time: 6–7 h · Prereqs: 27, 30
Objectives: color graphs; apply the chromatic number; use planarity and Euler's formula; appreciate the Four Color Theorem; apply coloring to scheduling/registers.
Sections: 33.1 Graph coloring and chromatic number · 33.2 Applications (scheduling, register allocation, maps) · 33.3 Planar graphs and Euler's formula · 33.4 Kuratowski's theorem (intro) · 33.5 The Four Color Theorem · 33.6 Greedy coloring and its limits · Summary, Project Checkpoint.
Key terms: graph coloring, chromatic number, planar graph, Euler's formula, Four Color Theorem.
Threads: anchor → community detection / scheduling in social-network setting; CS hook → register allocation in compilers.

Chapter 34: Network Flow and Matching

Difficulty: advanced · Time: 7 h · Prereqs: 29
Objectives: model flow networks; compute max flow (Ford–Fulkerson); apply max-flow/min-cut; solve bipartite matching.
Sections: 34.1 Flow networks · 34.2 The max-flow problem · 34.3 Ford–Fulkerson and augmenting paths · 34.4 The max-flow min-cut theorem · 34.5 Bipartite matching · 34.6 Applications (assignment, scheduling, image segmentation) · Summary, Project Checkpoint.
Key terms: flow network, max flow, min cut, augmenting path, Ford–Fulkerson, bipartite matching.
Threads: capstone synthesis of graph algorithms; CS hook → resource allocation.

Part VI — Advanced Topics and Synthesis

Where discrete math meets the theory of computation: what computers can recognize, what they can't compute at all, and what they can't compute efficiently. Then we synthesize everything.

Chapter 35: Automata and Formal Languages

Difficulty: advanced · Time: 7 h · Prereqs: 8, 12, 27
Objectives: build finite automata; relate DFAs/NFAs/regular expressions; apply the pumping lemma; place languages in the Chomsky hierarchy.
Sections: 35.1 Languages and the recognition problem · 35.2 Deterministic finite automata · 35.3 Nondeterministic finite automata and equivalence · 35.4 Regular expressions ↔ automata · 35.5 The pumping lemma (limits of regularity) · 35.6 Beyond regular: the Chomsky hierarchy · Summary, Project Checkpoint.
Key terms: alphabet, language, DFA, NFA, regular expression, pumping lemma, Chomsky hierarchy.
Threads: CS hook → regex engines, lexers; sets up computability.

Chapter 36: Computability and the Halting Problem

Difficulty: advanced · Time: 7 h · Prereqs: 10, 35, 5
Objectives: describe Turing machines; explain decidability; prove the halting problem undecidable; recognize undecidable problems via reduction.
Sections: 36.1 The Turing machine model · 36.2 The Church–Turing thesis · 36.3 Decidable vs. undecidable · 36.4 The halting problem is undecidable (diagonalization) · 36.5 Reductions and other undecidable problems · 36.6 What this means for programmers · Summary, Project Checkpoint.
Key terms: Turing machine, decidable, undecidable, halting problem, reduction, Church–Turing thesis.
Threads: payoff of Cantor (Ch. 10) + contradiction (Ch. 5). Threshold concept: undecidability.

Chapter 37: Complexity Theory — P, NP, and Beyond

Difficulty: advanced · Time: 7–8 h · Prereqs: 14, 30, 36
Objectives: define P and NP; explain NP-completeness; use reductions; state P vs. NP and its stakes; recognize NP-complete problems.
Sections: 37.1 Measuring difficulty: complexity classes · 37.2 P and NP · 37.3 Verification vs. solution · 37.4 NP-completeness and the Cook–Levin theorem · 37.5 Reductions and the NP-complete zoo (SAT, clique, TSP) · 37.6 Coping with intractability; P vs. NP · Summary, Project Checkpoint.
Key terms: P, NP, NP-complete, NP-hard, polynomial reduction, Cook–Levin theorem, SAT.
Threads: synthesizes logic (SAT), graphs (clique/TSP), complexity (Ch. 14).

Chapter 38: Coding Theory — Error-Correcting Codes (added)

Difficulty: advanced · Time: 7 h · Prereqs: 24, 26
Objectives: quantify error detection/correction with Hamming distance; build Hamming codes; understand linear codes over finite fields; place codes in real systems.
Sections: 38.1 The noisy channel problem · 38.2 Hamming distance and code rate · 38.3 Error-detecting vs. error-correcting codes · 38.4 Hamming codes · 38.5 Linear codes over $\mathrm{GF}(2)$ · 38.6 Real codes (Reed–Solomon: QR codes, CDs, deep space) · Summary, Project Checkpoint.
Key terms: code, codeword, Hamming distance, code rate, parity-check matrix, Hamming code, linear code, Reed–Solomon.
Threads: payoff of algebraic structures (Ch. 24) + error detection (Ch. 26); capstone option D.

Chapter 39: Capstone — Applying Discrete Mathematics

Difficulty: intermediate · Time: 8–10 h · Prereqs: broad (Parts I–V)
Objectives: integrate the Toolkit into a complete project; choose and justify a discrete-math model; communicate results.
Sections: 39.1 The Toolkit so far (inventory) · 39.2 Choosing a capstone · 39.3 Track A: an RSA encryption system · 39.4 Track B: a social-network analyzer · 39.5 Track C: a Sudoku solver (constraint satisfaction + logic) · 39.6 Track D: an error-correcting code · 39.7 Presenting your work · Summary.
Key terms: (synthesis — no new core terms).
Threads: all three anchors converge; Toolkit completed. Case studies = two fully worked tracks.

Chapter 40: Where Discrete Math Goes Next

Difficulty: beginner · Time: 4–5 h · Prereqs: none (capstone of ideas)
Objectives: map advanced directions; connect to other DataField CS books; plan further study.
Sections: 40.1 Combinatorial optimization and LP · 40.2 Advanced coding & information theory · 40.3 Ramsey theory and the probabilistic method (revisited) · 40.4 Category theory (a brief preview) · 40.5 Where these tools take you (algorithms, crypto, ML, PL) · 40.6 A reading path forward · Summary.
Key terms: (survey — pointers, not new core terms).
Threads: closes the four recurring themes; connects to the broader CS catalog.

End of outline. The companion 00-frontmatter/dependency-graph.mermaid shows the chapter dependency graph used to schedule the parallel build.