cs-068 — Peak Finding
| Field | Value |
|---|---|
| id | cs-068 |
| difficulty | Expert |
| topics | search, neighbours |
| lecture | lecture-17 |
| 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
Find a local maximum in a list (greater than its neighbours). Comparing neighbours safely at the edges; why 'a peak exists' needs an argument.
Your deliverable is the answer for the worked instance, the precondition stated, and the not-found behaviour demonstrated. 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: [1, 3, 4, 3, 1] -> peak at index 2 (value 4); edge peaks: [5,2] peak at 0; [2,5] peak at 1
- Output: returns any one local maximum index; a peak always exists (argument: climb uphill from anywhere)
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
- Compare neighbours safely at the ends: treat outside as -infinity. Why must a peak always exist?
- Sorted data is not just faster — it enables different algorithms.
- A scan is only as good as its stated precondition.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "If this scan ran 10,000 times a day, what would you precompute?"
Constraints and assumptions
- Difficulty: Expert (independent design decisions and proof-shaped arguments assumed).
- Topics: search, neighbours.
- 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: State the precondition that enables a faster method and quantify the gain.