Practice question · Multiple choice
Given a new problem, an experienced programmer often recognises it as a variant of something known - shortest path, or a scheduling problem - rather than inventing an algorithm. Why is recognition so much more productive than invention?
Hints
- What do you get for free when you recognise a problem as shortest-path?
- Ask what obligations you take on by inventing an algorithm instead.
Show the answer
C. Because a recognised problem brings a proved algorithm with known limits.
Why
Recognition brings a proved-correct algorithm, a known complexity, known edge cases and usually a tested implementation; invention means taking all of that on yourself. The mapping step is worth practising, 'assign staff to shifts' is bipartite matching, 'order tasks with dependencies' is topological sort. Recognising a problem as NP-complete is valuable too: it tells you to stop looking.
Practise Integrated Algorithm Design Practice
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Integrated Algorithm Design Practice
- A problem is shown to be NP-complete. Why is that useful news rather than merely bad news?
- For 'find the k most frequent words in a huge text', select every design decision the lesson endorses.
- The fastest algorithm for a problem in the abstract is the right choice regardless of the data and…
- Order the first five steps of the design workflow the lesson recommends.
- Match each data structure to the hot operation it makes fast.