Chapter 39 Key Takeaways — Capstone: Applying Discrete Mathematics

A scannable reference for the capstone. This chapter has no new core terms; it integrates the whole book. Reread this before starting your project.

The dmtoolkit inventory (your dependencies)

Module Built in Headline functions Math underneath
logic.py 1–3 truth_table, is_tautology, equivalent Propositional logic
sets.py 8 union, intersection, power_set, cartesian Set algebra
relations.py 12–13 is_equivalence, closure_transitive, topo_sort Relations, posets
combinatorics.py 15–17 perm_count, comb_count, permutations, combinations Counting
recurrences.py 6, 18–19 check_identity, solve_linear, fib Induction, recurrences
probability.py 20–21 simulate, expected_value, bayes Discrete probability
numbertheory.py 22–23 gcd, ext_gcd, sieve, mod_inverse, mod_pow, crt Number theory
crypto.py 24–25 rsa_keygen, rsa_encrypt, rsa_decrypt Public-key crypto
graphs.py 27–34 Graph, bfs, dfs, dijkstra, mst_kruskal, greedy_coloring, max_flow Graph theory
coding.py 26, 38 hamming_distance, hamming_encode, hamming_decode Error-correcting codes

The four tracks — decision table

Track System Leans on Core pieces Load-bearing theorem ⭐
A RSA encryption Ch. 22–25 rsa_*, mod_inverse, mod_pow $m^{ed}\equiv m \pmod n$ (Euler) ⭐⭐⭐
B Social-network analyzer Ch. 27–33 Graph, bfs, greedy_coloring BFS computes shortest distances ⭐⭐
C Sudoku solver Ch. 1–3, search backtracking (DFS), is_legal Backtracking is sound + complete ⭐⭐
D Error-correcting code Ch. 24, 26, 38 hamming_encode/decode/distance $d\ge3\Rightarrow$ corrects 1 error ⭐⭐⭐

Choosing rule: pick the part of the book you understood best (consolidate strength, don't patch weakness); match flavor (A/D = exact bits & numbers; B = messy data modeling; C = search); scope to one finished, defended system.

Track A — RSA system (formulas)

Step Operation
Key (from primes) $n = pq$, $\phi = (p-1)(q-1)$, $d = e^{-1} \bmod \phi$
Encrypt $c = m^e \bmod n$ (needs $0 \le m < n$)
Decrypt $m = c^d \bmod n$
Text → int bytes of message read big-endian as one integer
Constraint each block's integer must satisfy $m < n$ (else silent corruption)

Worked toy key (Ch. 25): $p=61, q=53, e=17 \Rightarrow n=3233, \phi=3120, d=2753$. Encrypt $65 \to 2790 \to$ decrypt $65$.

Track B — social-network analyzer (metric → tool)

Network question Graph quantity Tool
How connected is $v$? $\deg(v)$ g.degree(v)
Distance between two people unweighted shortest path bfs(g,s), read dist[t]
Most central person max-degree vertex max(vertices, key=g.degree)
Number of friend-clusters connected components repeated bfs
Network "width" diameter bfs from every vertex, max distance
Conflict-free grouping proper coloring greedy_coloring(g)

Idiom — components in $O(V+E)$: loop over vertices; for each unvisited one, bfs claims its whole component; a seen set skips the rest. Diameter is only well-defined on a connected graph.

Track C — Sudoku as a CSP

CSP part Sudoku
Variables the 81 cells
Domains digits 1–9 (givens fixed)
Constraints each row / column / 3×3 box "all different"
Goal a satisfying assignment (cf. SAT, Ch. 1/37)

Algorithm: backtracking = DFS over partial assignments. Find empty cell → try each legal digit → recurse → undo on failure (the backtrack line is mandatory). Generalized $n\times n$ Sudoku is NP-complete; the $9\times9$ board is easy because constraints prune hard.

Track D — error-correcting code (the one inequality)

$$\text{min distance } d \;\Rightarrow\; \text{detect } d-1 \text{ errors}, \quad \text{correct } \left\lfloor \tfrac{d-1}{2} \right\rfloor \text{ errors}.$$

Quantity Hamming(7,4)
Data / total bits 4 / 7
Parity bits 3
Minimum distance $d$ 3
Corrects 1 error per block
Code rate $4/7 \approx 0.57$

Decode = snap to nearest codeword. Correction works because Hamming distance is a metric: one flip lands distance 1 from the true word and (triangle inequality) $\ge 2$ from any other.

Presenting your work — write-up template

  1. Problem & model — the discrete-math objects you used (lead with this).
  2. Design & build — modules + new glue; functions with one-line contracts.
  3. Correctness — the central claim + its proof (cite earlier theorems).
  4. Evidence — inputs, outputs, what you tested and what you did not.
  5. Complexity & limits — running time; honest scope.

Common pitfalls

Pitfall Fix
Doing all four tracks "a little" One finished, defended system beats four stubs
RSA: ignoring $m < n$ Block the message; each block's integer $< n$
Sudoku: missing the backtrack (grid[r][c]=0) Always undo a failed choice
Coding: assuming 2 flips are correctable $d=3$ corrects only 1; 2 flips → wrong codeword
"All tests passed" = "correct" Tests demonstrate; only a proof guarantees
Overclaiming ("secure", "efficient", "robust") State the exact guarantee, no more

Toolkit additions this chapter

  • dmtoolkit/__init__.py — re-exports the headline functions (public front door).
  • self_test() — an integration test asserting one round-trip per major module (gcd, RSA, BFS, Hamming) still composes. Returns True when all pass.
  • The package is now complete: 10 modules built from scratch across 39 chapters.

The four themes, landed

  1. Discrete math is the language of CS — every track is a discrete-math model running as code.
  2. Proofs guarantee correctness — each track ships with a correctness argument, not just tests.
  3. Abstraction is the master tool — the right model (graph, $\mathbb{Z}_n$, CSP, code) makes the code fall out.
  4. Computation and proof are complementary — demonstrate with runs, guarantee with proofs; never confuse them.