Module 1: Algorithm Analysis & Design Paradigms: Case Studies
These cases turn asymptotic analysis into engineering judgment: choosing an approach, proving why it works, and measuring whether the implementation matches the model.
Case Study 1: The Dashboard Query That Became Quadratic
Scenario: A team adds a dashboard that compares every active customer against every active invoice to find overdue accounts. It works for 2,000 records in staging, but production has 1.8 million invoices and the job runs for hours.
Source anchor: MIT OpenCourseWare 6.006 complexity material and Google Benchmark user guide.
Module concepts:
- asymptotic analysis
- input growth
- hash-based lookup
- benchmark design
Wrong Approach
Tune the nested loop, add logging, and increase the job timeout.
Better Approach
Model the work first: comparing every customer with every invoice is O(C * I). Build an index from customer ID to invoice summary, turning lookup into expected constant-time access, then benchmark across growing input sizes to confirm the slope changed.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Keep nested loop | Minimal code change | Runtime grows too fast |
| Build hash index | Large speedup | Extra memory and index construction |
| Push aggregation to database | Uses existing engine | Requires query-plan review |
Failure Mode
A staging test with tiny data hides the production growth curve.
Required Artifact
Produce a complexity note and benchmark table for 1k, 10k, 100k, and 1M invoices, including runtime, memory, and expected asymptotic shape.
Project / Capstone Connection
Use this artifact for every algorithm in the Semester 2 algorithms library: hypothesis first, measurement second.
Case Study 2: Greedy Scheduling That Looks Right But Fails
Scenario: A support platform assigns tickets to engineers. A developer greedily picks the ticket with the shortest estimated time first to maximize throughput. VIP tickets then miss deadlines because urgency was ignored.
Source anchor: The module's greedy-choice and exchange-argument lessons.
Module concepts:
- greedy algorithms
- counterexamples
- correctness proof
- objective function design
Wrong Approach
Assume a greedy rule is correct because it performs well on examples.
Better Approach
State the objective precisely: minimize total completion time, maximize number before deadline, or minimize weighted lateness. Test the greedy rule against small exhaustive cases, search for counterexamples, and require an exchange argument before trusting it.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Shortest job first | Simple and often efficient | Wrong for deadline or priority objectives |
| Earliest deadline first | Protects deadlines | May reduce total throughput |
| Dynamic programming or search | Handles richer constraints | Higher implementation cost |
Failure Mode
The algorithm optimizes the wrong metric and appears successful until stakeholders inspect missed VIP deadlines.
Required Artifact
Write a problem statement with objective, constraints, proposed greedy rule, counterexample search, and proof obligation.
Project / Capstone Connection
Add this proof-obligation section to any project algorithm that claims to be greedy.
Case Study 3: Divide and Conquer for Log Aggregation
Scenario: A telemetry pipeline merges sorted log shards from many services. The first implementation repeatedly concatenates arrays and sorts the entire result after each shard arrives.
Source anchor: The module's divide-and-conquer and recurrence-analysis concepts.
Module concepts:
- divide and conquer
- recurrence analysis
- merge strategy
- practical constants
Wrong Approach
Call a general sort after every append because sorting is O(n log n) and the built-in sort is fast.
Better Approach
Use the sorted structure already present. Merge shards pairwise or with a heap-based k-way merge, then analyze the recurrence and memory behavior. Compare the practical crossover point because built-ins may win for small inputs.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Re-sort after each shard | Easy implementation | Repeats work |
| Pairwise merge | Clear divide-and-conquer shape | Needs buffer planning |
| Heap k-way merge | Good for many shards | More complex iterator handling |
Failure Mode
The team quotes O(n log n) for a single sort but misses repeated sorting across many shards.
Required Artifact
Create a recurrence or cost model for repeated sort, pairwise merge, and k-way merge, plus a benchmark plan that finds the crossover point.
Project / Capstone Connection
Use the same model for comparing multiple correct algorithms in the portfolio artifact.
Case Study 4: Backtracking Search With Real Pruning
Scenario: A course planner must choose a valid semester schedule from prerequisites, time slots, credit limits, and required electives. A brute-force search over every course subset times out.
Source anchor: The module's exhaustive search, pruning, and debugging-complex-algorithms lessons.
Module concepts:
- backtracking
- pruning
- invariants
- search-tree debugging
Wrong Approach
Randomly reorder the search and hope it finds a valid plan sooner.
Better Approach
Define partial-solution validity: no time conflict, credits within limit, prerequisites satisfied or scheduled earlier. Prune as soon as an invariant fails, order choices by most constrained course first, and log search-tree statistics so pruning is visible.
Tradeoff Table
| Choice | Gain | Cost |
|---|---|---|
| Brute force | Simple correctness story | Explodes combinatorially |
| Backtracking with invariants | Major pruning | Requires careful invariant design |
| Constraint solver | Powerful modeling | Adds dependency and learning cost |
Failure Mode
The algorithm keeps exploring schedules that already violate credit limits.
Required Artifact
Produce a search-state definition, pruning rules, invariant tests, and a trace from one rejected branch.
Project / Capstone Connection
Use this trace format when explaining any exponential algorithm in the semester project.
Source Map
| Source | Use it for |
|---|---|
| MIT OpenCourseWare 6.006 complexity material | Complexity vocabulary and growth-rate reasoning. |
| Google Benchmark user guide | Benchmark families and asymptotic measurement discipline. |