Module 2: Combinatorics & Graph Theory: Case Studies
These cases connect counting and graph models to engineering problems where the model choice determines the solution.
Case Study 1: Counting Test Configurations
Scenario: A QA team needs to test browsers, locales, payment methods, and account types. The first plan lists cases manually and misses combinations.
Source anchor: MIT Mathematics for Computer Science.
Module concepts:
- product rule
- combinations
- coverage
- constraints
Wrong Approach
Add test cases until the list feels large enough.
Better Approach
Model independent dimensions, multiply choices for full coverage, then add constraints that remove impossible combinations. Decide where pairwise coverage is acceptable and where full coverage is required.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Manual list | Easy start | Misses cases |
| Full Cartesian plan | Complete | Can explode |
| Pairwise plan | Practical coverage | Not exhaustive |
Failure Mode
A rare browser-locale-payment combination fails because it was never counted.
Required Artifact
Produce a configuration-count table with dimensions, total combinations, invalid combinations, and selected coverage strategy.
Project / Capstone Connection
Use the same counting table later for test-matrix design, rollout planning, and scenario coverage in production-facing systems.
Case Study 2: Course Prerequisites as a Graph
Scenario: A degree planner stores course prerequisites as text. A learner cannot detect cycles or generate a valid semester order.
Source anchor: MIT Mathematics for Computer Science.
Module concepts:
- directed graphs
- DAGs
- topological order
- cycles
Wrong Approach
Sort courses by course number and assume lower numbers come first.
Better Approach
Represent courses as nodes and prerequisite relationships as directed edges. Check for cycles, then topologically sort to produce a valid order.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Text prerequisites | Human-readable | Hard to analyze |
| Directed graph | Enables algorithms | Needs clean data |
| Manual advising | Flexible | Does not scale |
Failure Mode
Two courses accidentally require each other and the planner never reports the cycle.
Required Artifact
Draw the prerequisite graph, identify any cycle, and produce one valid topological ordering.
Project / Capstone Connection
Reuse prerequisite graphs later for build pipelines, task scheduling, and dependency planning in larger projects.
Case Study 3: Social Recommendations and Degree
Scenario: A social app recommends accounts with many mutual connections. Popular accounts dominate recommendations even when they are not relevant.
Source anchor: MIT Mathematics for Computer Science.
Module concepts:
- graph degree
- paths
- bipartite thinking
- model limitations
Wrong Approach
Recommend the highest-degree node because it is connected to many users.
Better Approach
Define the graph model and the objective. Use mutual-neighbor counts, normalize for popularity when needed, and test cases where high degree is misleading.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Highest degree | Simple ranking | Popularity bias |
| Mutual neighbors | Better relevance | Can miss new accounts |
| Normalized score | Reduces bias | Harder to explain |
Failure Mode
The app recommends celebrities to everyone and fails to surface useful peers.
Required Artifact
Create a small graph, compute degree and mutual-neighbor scores, and explain the ranking difference.
Project / Capstone Connection
Carry this graph-scoring explanation into recommendation, social, fraud, or dependency-analysis features in later capstone work.
Source Map
| Source | Use it for |
|---|---|
| MIT Mathematics for Computer Science | Counting methods, graph models, and proof-backed reasoning. |