Day 69 — Modeling workshop

Updated

July 30, 2026

Day 69 — Modeling workshop

Stage VI · workshop day
Goal: Convert 8–12 word problems into formal \(G=(V,E)\) plus precise questions (path, color, topo, matching, short path, Euler/Hamilton, tree/MST); practice the writeup template for Gate VI.

Why this matters

Gate VI and real engineering reviews reward clear models, not vague gestures. Today is deliberate practice: every problem gets the same template until it is automatic.

Writeup template (required format)

For each problem, write:

Name:
Vertices V:
Edges/Arcs E: (directed? weighted?)
Graph class notes: (simple/multi/bipartite/DAG candidate…)
Question(s) in graph language:
Method/tool:
Answer or plan (hand-solvable instance if numbers given):
Pitfall / alternative model:

Method selection guide (Stage VI)

Story cue	Model & tool
Prerequisites / build order	DAG + topo
Circular depends	Directed cycle detect
Fewest hops	BFS
Min time/cost paths	Dijkstra / BF
Wire all cheaply	MST Kruskal/Prim
Conflicts / slots	Coloring
Assign jobs one-to-one	Bipartite matching + Hall
Tour every street	Euler
Tour every city	Hamilton (hard)
Hierarchy unique paths	Tree checks
Reliability single point	Cut vertex/edge

Warm-up models (short)

W1. Five courses; prereq list.
W2. Four friends; friendships; distance between A and D.
W3. Three variables live ranges overlapping.

W4. Delivery truck must drive every street downtown at least once.
W5. Sales rep must visit each client city exactly once and return.

Workshop problems

Solve at least 8 in full template form; stretch for 12.

Set A — Dependencies & order

A1. Software packages. Packages {P,Q,R,S}; depends: P→Q, P→R, Q→S, R→S (arc means “uses”). Is install-by-topo possible? List a valid order if we orient “build dependency first” consistently—state orientation.

A2. Project tasks. Tasks A(2d), B(3d), C(1d), D(4d), E(2d); precedences A before C, B before C, C before E, D before E. Model DAG; find critical path length.

A3. Spreadsheet. Cells A1, B1, C1 with formulas A1=B1+1, B1=C1+1, C1=A1+1. Model; diagnose.

Set B — Networks & paths

B1. Subway. Stations S,A,B,C,T with undirected edges as Day 62 G1. Fewest hops S to T?

B2. Weighted roads. Same vertices; weights as Day 64 Ex.1. Min driving time S to T?

B3. Fiber. Towns 1..5; possible links with costs you choose; connect all min cost—MST.

B4. One-way streets. Directed city; weak vs strong connectivity question.

Set C — Assignment & conflict

C1. Jobs/machines. Jobs J1–J3, machines M1–M3; edges for compatible pairs (specify); Hall check for full assignment.

C2. Exam scheduling. Courses {1,2,3,4}; conflicts {12,23,34,14}; min exam slots = \(\chi\).

C3. Register lite. Variables a,b,c,d; overlaps ab,bc,cd,ac; registers needed.

Set D — Tours & structure

D1. Snowplow. City graph degrees all even except two; what tour exists?

D2. Sales route. 5 cities complete graph—name the hard problem.

D3. Tree check. n=6, edges 5, connected—tree? Unique path?

D4. Bipartite zoo. Animals–habitats incidence; matching interpretation.

Set E — Systems & states

E1. Protocol. States {Idle, Auth, Active, Error}; transitions Idle→Auth→Active→Idle, Auth→Error→Idle. Reachable from Idle? Cycles?

E2. Feature flags. 3 flags; transitions flip one bit; state graph is 3-cube—diameter?

E3. Call graph. Functions main, f, g, h; calls main→f, f→g, g→f, main→h. SCCs? Dead code?

Set F — Rapid modeling (template skeleton only)

For each, fill V, E meaning, question type in ≤4 lines.

F1. Classroom seats; two students cannot sit adjacent if they conflict—assign seats?
F2. Airline crews; flights as vertices; edge if same-day overlap—crew count?
F3. Makefile targets and dependencies.
F4. Escape routes from building floor plan (portals as edges).
F5. Matching interns to projects with skill edges.
F6. Chip modules; wires as edges; can you draw with no crossing? (planarity ask)

Worked solutions (selected)

A1. Orient arc \(X\to Y\) if \(X\) must be installed before \(Y\) (i.e. \(Y\) depends on \(X\)): if P depends on Q and R, then Q→P, R→P, etc. Rebuild from English carefully. Suppose depends “P requires Q and R; Q requires S; R requires S”: arcs S→Q, S→R, Q→P, R→P. Topo: S, Q, R, P or S, R, Q, P. No cycle.

A2. Longest path: e.g. B(3)–C(1)–E(2)=6 or D(4)–E(2)=6 or A(2)–C–E=5. Critical length 6.

A3. Cycle A1–B1–C1–A1: circular reference; not a DAG.

B1. dist=2 via S–B–T.

B2. d(T)=5 path S–A–B–C–T.

C2. Conflict = C_4: \(\chi=2\).

C3. Interference path/cycle: a–b–c–d + a–c ⇒ odd structure; \(\chi=3\) (triangle a,b,c).

D1. Eulerian trail between the two odd-degree vertices.

D2. TSP / Hamilton cycle optimization.

D3. Yes tree if connected with 5 edges on 6 verts.

E3. SCC {f,g}; {main}; {h}; all reachable from main except nothing dead if all called; h leaf.

Self-score

Set	Min problems	Points	Score
A	2	15	/15
B	2	15	/15
C	2	15	/15
D	2	15	/15
E	1	10	/10
Template quality	all	30	/30
Total		100	/100

Pass ≥ 75. Template quality: clear V, E, question, method.

Exercises (complete the rest)

Full template for A1–A3.
Full template for B1–B4.
Full template for C1–C3.
Full template for D1–D4.
Full template for E1–E3.
Invent a dependency problem with a cycle; show Kahn fails.
Invent a matching problem that fails Hall; exhibit \(S\).
Model DNS hierarchy as a tree; what do cuts mean?
Model git commits with merges as DAG; topo = ?
Why CFG path count ≠ test adequacy alone.
Convert social “influencer” into degree + betweenness awareness.
MST vs TSP on same towns—different questions.
Color a conflict graph from a real weekly schedule of yours.
Dijkstra on a 5-vertex digraph you create.
Euler or Hamilton: museum hallway vs city landmarks.
State explosion: 10 boolean vars → how many states?
Bridge in a company org chart modeled as graph.
Peer review: swap models with a peer (or future you) and critique.
Challenge: model MapReduce / dataflow as DAG; critical path.
Write Gate VI modeling section practice under 25 minutes.
List 5 mistakes from your first drafts.
Redo worst writeup.
Connect one model to Day 53 counting (state space size).
Connect one model to Day 65 Hall.
One-page portfolio of 3 best models for Gate VI.

CS connection

Workshop scenarios are drawn from engineering practice. Carry the template into design docs: “Vertices are… Edges mean… We ask…”

Common pitfalls

Pitfall	What to do instead
Missing direction	Always say directed/undirected
Question in English only	Translate to path/color/…
Over-large model	Minimal V that captures the ask
Solving without model	Template first, numbers second
Hard problem when easy fits	Recheck Euler vs Hamilton etc.

Checkpoint

Template automatic
≥ 8 full writeups
Self-score ≥ 75
One dependency + one matching + one short path
One hard-vs-easy tour contrast
Portfolio of 3 models ready for Gate VI

Two personal takeaways:

Deepening notes

Template speed run (5 min each)

Practice blank template fills:

npm depends
subway hops
exam conflicts
job matching
weighted roads
snowplow
FSM protocol
MST fiber

Peer critique rubric

Item	0–2 pts
V precise
E meaning clear
Question graph-theoretic
Method fits
Answer/plan correct

Extra invented problems

I1. Hospital rooms & equipment sterilization constraints.
I2. Compiler basic-block scheduling with latencies.
I3. Social “block” undirected vs “mute” directed.
I4. Warehouse robots aisle graph Euler.
I5. Course waitlist matching bipartite.

Gate VI modeling preview

You will need: one full package/exam/matching model; one shortest-path or MST numeric; Euler vs Hamilton paragraph. Prepare three templates tonight.

Timed set (40 minutes)

Do full templates for:

A1 packages
B2 weighted roads
C2 exams
C1 matching
D1 snowplow
E1 protocol
Invent MST fiber 5 towns
Invent call graph SCC

Score: 5 pts template structure + 5 pts correct analysis each = /80.

Common template failures checklist

Forgot directed vs undirected
Edges mean two different English things
Question left in English only
Used Hamilton for street traversal
Dijkstra on unweighted hops
Topo on undirected graph
Hall without checking all \(S\)
No small sanity instance

Three portfolio models (finalize tonight)

Portfolio 1 — Dependencies
Portfolio 2 — Assignment/matching
Portfolio 3 — Routing/shortest path

Write each to Gate quality; bring into Day 70.

Fully worked templates (exam quality)

W4 — Snowplow / streets.

Name: Downtown street inspection
Vertices V: intersections
Edges E: undirected streets (multiedges if needed)
Question: Euler trail/circuit?
Method: count odd-degree vertices; Hierholzer if 0 or 2 odds
Pitfall: modeling as Hamilton (cities) instead of edges

W5 — Sales tour.

Name: Client tour
Vertices V: client cities (+ depot)
Edges E: roads (often complete weighted)
Question: Hamilton cycle / TSP
Method: small n backtrack; large n heuristics; not Euler
Pitfall: calling it Chinese postman

C1 sketch. Bipartite \(L=\) jobs, \(R=\) machines; edge = compatible. Hall on all \(S\subseteq L\). Max matching algorithm if numbers given.

A3 full. Cells form directed graph formula-reference; cycle ⇒ circular reference; topo sort impossible; spreadsheet engine error.

Deep dive — Minimal models

Good models omit irrelevant detail. If the question is only “can we order builds?”, weights do not matter—use an unweighted DAG. If the question is “min travel time,” unweighted BFS is wrong—use Dijkstra. If conflicts are the only constraint, coloring needs no distances. Ask what decision changes if you delete a feature from the model. If none, delete it.

Synthesis — Gate VI writeup muscle

Template first, always.
Name graph class (DAG, bipartite, weighted, …).
Translate the English ask into path / color / match / Euler / Hamilton / MST / topo.
Pick the lightest correct algorithm/theorem.
Sanity on a tiny instance.
Note the classic mix-up (Euler↔︎Hamilton, BFS↔︎Dijkstra, undirected↔︎directed).

S1. Full template + solution plan for A2 critical path.
S2. Full template for C2 exam \(\chi\).
S3. Full template for D1 snowplow.
S4. Invent and template a problem that looks like Hamilton but is Euler.
S5. One-page portfolio: dependency + matching + shortest path, Gate-ready.

Tomorrow

Day 70 — Gate VI: model + handshaking + tree check + BFS levels + DAG topo + bipartite/matching + shortest path on a tiny weighted graph.