cs-072 — The Kth Element
| Field | Value |
|---|---|
| id | cs-072 |
| difficulty | Expert |
| topics | sorting, selection |
| lecture | lecture-18 |
| 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 the k-th smallest without fully sorting (partial selection via repeated min-removal on paper, then discuss doing better). Analysis reasoning from first principles.
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: [7, 1, 5, 3, 9, 2], k = 3 -> answer 3; k = 1 -> 1; k = 6 -> 9
- Output: kth smallest via sort is O(n log n); repeated-min selection is O(kn) - compare on n=10000, k=3
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
- Two honest methods: sort and index, or find-min k times. Which wins depends on k vs log n.
- 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: sorting, selection.
- 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: Add a stable tie-break rule and show a case where it matters.