cs-095 — The Prerequisite Chain
| Field | Value |
|---|---|
| id | cs-095 |
| difficulty | Intermediate |
| topics | graphs, topological order |
| lecture | lecture-24 |
| estimated time | 5-minute attempt + 10-minute discussion |
| prerequisites | loops, lists, and tracing from lectures 1-6 |
| objective | choose the technique, trace it faithfully, and defend the boundary behaviour |
| solution | held by the instructor; discussed after the attempt |
Problem
Order courses so prerequisites come first (topological sort). Detect cycles as 'impossible semester plans'.
Your deliverable is the graph model (nodes/edges), the traversal result for the worked instance, and the unreachable-case behaviour. 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: prereqs: CS2 needs CS1; DS2 needs CS1 and Stats; AI needs CS2 and DS2
- Output: order: CS1, Stats, CS2, DS2, AI (or CS1, CS2, Stats, DS2, AI); cycle -> impossible
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
- Kahn's algorithm: repeatedly take a course with no remaining prerequisites; if you get stuck, there is a cycle.
- The modelling choice (what is a node?) is the actual problem.
- BFS layers are distances — that is why it answers 'fewest steps'.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "Where does the algorithm report 'unreachable', and what should the user see?"
Constraints and assumptions
- Difficulty: Intermediate (loops and lists assumed).
- Topics: graphs, topological order.
- Classroom-scale inputs unless the problem says otherwise.
- Time-box: about five minutes for the plan and trace; finishing the details is a bonus, defending the method is the target.
- 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: Re-model with the opposite edge direction and describe what the traversal gives.