cs-040 — The Anagram Detector
| Field | Value |
|---|---|
| id | cs-040 |
| difficulty | Advanced |
| topics | strings, normalisation |
| lecture | lecture-10 |
| 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
Decide if two phrases are anagrams ignoring case, spaces, and punctuation. Normalisation as the key idea; two implementation routes (sort vs count).
Your deliverable is the verdict for the worked instance, the normalisation rules you applied, and one input that exposes a missing rule. 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: "Dormitory" / "dirty room!"; "astronomer" / "moon starer"; "hello" / "world"
- Output: True, True, False - after normalising (lowercase, letters only)
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
- Normalise both, then either sort the characters or count them - count is O(n), sort is O(n log n).
- Most string tasks are: normalise, then a simple check.
- Index arithmetic is where string bugs live — guard the ends first.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "Which normalisation steps are safe to merge, and which change the answer if done in the wrong order?"
Constraints and assumptions
- Difficulty: Advanced (functions, dictionaries, and algorithmic reasoning assumed).
- Topics: strings, normalisation.
- 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: Normalise the input differently and show the answer does (or does not) change.