cs-052 — The Consensus Checker
| Field | Value |
|---|---|
| id | cs-052 |
| difficulty | Expert |
| topics | dictionaries, voting, logic |
| lecture | lecture-13 |
| estimated time | 5-minute attempt + 10-minute discussion |
| prerequisites | the full Block I-III toolbox and proof-shaped reasoning |
| objective | make and justify design decisions where the method itself is the challenge |
| solution | held by the instructor; discussed after the attempt |
Problem
Given ballots ranking three options, compute pairwise preferences and detect whether a majority prefers A over B and B over C while C beats A overall (a cycle). Fairness emerges from data.
Your deliverable is the mapping/set answers for the worked instance, the key choice justified, and the tie-break rule stated. If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.
Examples
- Input: 3 ballots: A>B>C, B>C>A, C>A>B
- Output: A beats B 2-1; B beats C 2-1; C beats A 2-1 - a Condorcet cycle: no majority winner
Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.
What to notice
- For each pair (X, Y), count ballots ranking X above Y. All three pairs can point in a circle.
- A dictionary turns 'search for the item' into 'look it up' — that is the whole win.
- Sets answer yes/no questions; dictionaries answer how-many questions.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "What breaks if two different real-world things map to the same key — and how would you detect it?"
Constraints and assumptions
- Difficulty: Expert (independent design decisions and proof-shaped arguments assumed).
- Topics: dictionaries, voting, logic.
- Classroom-scale inputs unless the problem says otherwise.
- Time-box: about five minutes for the attack plan; the full argument may exceed the box - outline the proof strategy instead of grinding details.
- Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.
Hints and extension
- First nudge: identify the pattern the worked instance uses before computing anything.
- If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
- After the reveal, attempt the extension below before the next lecture.
- Extension challenge: Invert the lookup (value to keys) and state when collisions appear.