Self-Assessment Quiz: Capstone — Applying Discrete Mathematics

Twenty questions to check that you can map the Toolkit to its mathematics, reason about each track's correctness, and tell a proof from a passing test. The capstone is about integration, so several questions span more than one track. Answer before opening the key. Aim for 16+.

Question 1

A capstone project, as the chapter defines it, differs from a homework problem mainly because it:

A) is always harder mathematically B) integrates many ideas, has design decisions with no single right answer, and ends in something you can show another person C) requires no proof, only working code D) must use all ten Toolkit modules at once

Question 2

Which Toolkit module is the operational core of Track A (RSA), and which two of its functions are named in the chapter as the heart of encryption/decryption?

A) crypto.py; rsa_keygen and sieve B) numbertheory.py; mod_pow and mod_inverse C) numbertheory.py; gcd and crt D) coding.py; hamming_encode and hamming_decode

Question 3

In Track A, the constraint $m < n$ on each message block exists because:

A) larger messages are slower to encrypt B) arithmetic happens in $\mathbb{Z}_n$, so any $m \ge n$ collides with $m \bmod n$ and cannot be recovered C) the public exponent $e$ requires it D) UTF-8 forbids large code points

Question 4

With the toy key $n = 3233$, encrypting text_to_int("Hi") == 18537 directly (no blocking) and then decrypting returns:

A) 18537 — it works fine B) an exception is raised C) $18537 \bmod 3233 = 2372$ — silent corruption D) 0

Question 5

The load-bearing theorem under Track A — that decryption inverts encryption — is justified by:

A) the pigeonhole principle B) Euler's theorem (with the Chinese Remainder Theorem patching the non-coprime case) C) the handshaking lemma D) the triangle inequality

Question 6

In Track B, "six degrees of separation" is, in graph-theory terms, a claim about the network's:

A) chromatic number B) maximum degree C) diameter D) number of edges

Question 7

Track B's components(g) loops over every vertex but calls bfs only once per component. The mechanism that arranges this is:

A) sorting the vertices first B) the seen set, which absorbs each BFS's whole component so later vertices in it are skipped C) Dijkstra's relaxation step D) the queue used inside BFS

Question 8

On the chapter's six-person graph, the most-central (maximum-degree) vertices are:

A) Ana only B) Cam only C) Cam and Dev (a genuine tie at degree 3) D) all six are tied

Question 9

Track B's correctness rests on a property of BFS proved in Chapter 28. That property is:

A) BFS visits every edge exactly once B) dist[v] equals the fewest-edges distance from the source for every reachable $v$ C) BFS is faster than DFS D) BFS finds a minimum spanning tree

Question 10

Track C models Sudoku as a constraint satisfaction problem. The "all different" rule for one row, with 9 cells, is a conjunction of how many pairwise inequalities?

A) 9 B) 18 C) 36 D) 81

Question 11

The Track C solver's solve function is, structurally, which kind of search?

A) breadth-first search B) depth-first search over the tree of partial assignments (backtracking) C) Dijkstra's algorithm D) a greedy algorithm

Question 12

Deleting the line grid[r][c] = 0 from the Sudoku solver breaks it because:

A) the recursion never starts B) a digit that led to a dead end is left in the grid as the loop tries the next digit, corrupting the constraints for all later cells C) it makes the search breadth-first D) is_legal stops working

Question 13 (True/False, justify)

True or false: The Track C solver's completeness (it finds a solution whenever one exists) follows because it performs an exhaustive depth-first traversal of a finite tree. Justify in one sentence.

Question 14

For Hamming(7,4) with minimum distance $d = 3$, the number of errors it can correct per block is:

A) 0 B) 1 C) 2 D) 3

Question 15

The single-error-correction proof for Track D uses which property of Hamming distance as its key step?

A) it is always even B) it satisfies the triangle inequality (it is a metric) C) it equals the number of 1-bits D) it is bounded by the code rate

Question 16 (True/False, justify)

True or false: If two bits flip in one Hamming(7,4) block, the decoder reports an error and refuses to decode. Justify in one sentence.

Question 17

The code rate of Hamming(7,4) is $4/7$. This number represents the trade-off between:

A) speed and memory B) robustness (correcting power) and efficiency (throughput) C) encoding and decoding time D) bits and bytes

Question 18 (Short answer)

The chapter says a system "is correct because the pieces it composes are correct." In Track B, name the two derived metrics (besides dist itself) that are correct because BFS distances are correct, and state in one phrase why each inherits correctness.

Question 19 (Short answer)

A capstone write-up reports "I tested decryption on 10,000 random messages and all decrypted correctly." In one sentence each: (a) why is this not a proof of correctness, and (b) what single sentence converts the demonstration into a guarantee?

Question 20 (Short answer)

List, in order, the five sections of the §39.7 technical write-up template, and name the one section that "carries the mathematics" of the project.

Answer Key

Topics to review by question