Semester 1 Project: A Defensible Graph Investigation
Purpose and budget
Build a small reproducible investigation that counts triangles exactly, estimates them by sampling, and shows the graph through an interactive geometric view. Budget 18–26 additional hours, included in the semester integration budget. Reuse the six module notebooks, lab utilities and proof artifacts. This replaces the previous multi-project portfolio and fixed 20-page/15-proof quotas.
Fixed contract
Use finite simple undirected graphs with vertices 0..n-1, n<=40 for the required experiment. Reject self-loops and unknown vertices; reject or explicitly canonicalise duplicate edges before sampling. Include empty and disconnected graphs. Preserve isolated vertices. Store graph provenance and seeds locally.
For each edge e=(u,v), let c(e) count common neighbours. If m>0, sample k>=1
edges uniformly and independently with replacement and estimate the number of
triangles by (m/3) * mean(c(e)). If m=0, return exact zero without sampling.
This is an additive-error investigation; relative error is undefined at zero.
Milestones and evidence
| Milestone | Work | Reused module evidence |
|---|---|---|
| 1: model | Contract, graph fixtures, experiment hypothesis and independent triple-enumeration oracle | Proof and graph models; Module 5 specification |
| 2: exact reasoning | Prove sum c(e)=3T and trace(A cubed)=6T; compare all three counts | Module 1 proof discipline, Module 2 counting, Module 4 matrices |
| 3: experiment | Implement sampling, derive expectation and variance, compare several k values over independent seeds | Module 3 experimental protocol and uncertainty |
| 4: interactive evidence | Show nodes/edges, rotate coordinates, select an edge and display its common neighbours | Module 4 transformations and Module 5 boundary checks |
| 5: changed case and defense | Change one assumption, repair affected claims, reproduce and explain the limits | Module 5 handoff and every module's delayed review |
Use at least these fixtures: empty graph; triangle plus a tail (edges 01,12,02,23); four-cycle; four-cycle with one diagonal. For additional small graphs, compare oracle results exhaustively over all simple undirected graphs on up to four vertices. Test invalid inputs separately from valid graphs with zero triangles.
Experiment design
Before running, state the prediction that mean squared error falls like 1/k under
the specified unbiased model. Derive Var(estimate)=m*m*Var(c)/(9*k) from
independent draws. Use k=10,100,1000 across at least 30 independent recorded seeds
per nonempty fixture. Retain all runs. Report signed error, mean absolute error,
mean squared error and the theoretical variance. Small samples can fluctuate;
do not force observed ratios to match a prediction. Use the exact finite edge
distribution to calculate Var(c), not a second noisy estimate when exact values
are available. Label any confidence interval by method and assumptions.
Record operation counts and, if timing, the workload, machine, warm-up and timer boundary. Report uncertainty and the observed effect size between k settings. Do not infer a universal speed claim or causation from one selected graph.
Required visual and numerical evidence
Implement a small offline interactive graph view, for example HTML/SVG with labelled keyboard-accessible controls. Selecting an edge must identify its common neighbours in text as well as visually. Rotation must preserve adjacency and, within declared numerical tolerance, pairwise distances. A static screenshot alone does not satisfy the interaction requirement.
Use an independent coordinate-distance check as the geometry oracle. Compare two rotation angles and repeated rotations; record error relative to the initial coordinates. Reuse one Module 4 conditioning example to explain why a small residual does not guarantee a small solution error. Record actual render/update measurements for declared graph sizes and browser/environment; do not write a latency result before measuring. Explain one alternative view and one perception choice (such as text plus highlighting rather than colour alone).
Deliverables and defense
One README with reproduction commands; source and fixtures; proof notebook; experiment output with environment/provenance; interactive view; numerical and performance evidence; a decision log; and assistance declaration. A script plus Markdown is an acceptable reproducible notebook; a notebook server is optional. Keep the concise review narrative near 2–4 pages, linking full evidence.
Change exactly one assumption: sample without replacement, allow directed edges, or cap search by time. State which formulas/statuses survive and which do not; implement and check a bounded variant where feasible. An honest unresolved changed-case analysis can meet the handoff requirement, but cannot replace the working core contract. Defend a fresh fixture without consulting the key.
Every rubric category is required, including the empirical evidence strand. Independent review remains pending until a real reviewer has performed it; a self-review can be recorded as such. Carry the inspected artifacts into Semester 2.
Integer arithmetic appendix
Attach the already completed cyclic probe audit as a separate small appendix; do not force modular arithmetic into the triangle estimator or rebuild the lab. Preserve the complete-solution proof and a changed stride. Its work is included in the integer module allowance. The rubric requires this evidence alongside the original graph investigation.
Calculus appendix — reused evidence
Attach the approximation audit as a separate appendix. Reuse its density and numerical experiments rather than adding calculus artificially to the discrete triangle estimator. Preserve exact calculations, retained output, distinct error budgets and the changed-rate case. The calculus module allowance includes this evidence.
Probability inference appendix — reused evidence
Attach the inference memo and PS9–PS12 evidence. Keep its three model examples separate from the graph estimator. The 25–35 hour probability extension already includes this work; no additional experiment is required here.
Cross-module connections
Complete the model, units and error check during the existing integration review. Its four subchecks must each reach level 2 under the existing probability, numerical-judgment and calculus categories; no extra semester hours or replacement of module gates is implied.