2.2.2 - Recognising computational problems
Before writing an algorithm, decide what problem it is supposed to solve. You will turn a messy description into a precise computational task, separate its responsibilities and keep only the information needed by a useful model.
Decide what a computer can solve
A computational problem can be expressed using represented inputs, a defined result and operations that a computer can carry out. Calculations, comparisons, searching and storing data are suitable operations. A repeatable rule allows the same process to handle many records consistently.
Computational problem
A task with represented inputs, a defined required result and operations a computer can carry out. A vague aim needs explicit criteria before it becomes an executable rule.
A club wants to allocate available courts to booking requests. Each request can be represented by a member identifier, start time, duration and court type. Court availability can be stored. The rules might forbid overlapping bookings and choose the earliest available suitable court. These explicit comparisons make allocation amenable to an algorithm. Repeating the rule for hundreds of requests is a useful reason to automate it.
“Make every member happy” is not yet an executable rule. Happiness has no specified measurement, and two members may want the same court. A human must decide the priorities and acceptable compromises. A program can then optimise a measurable proxy, such as the number of accepted requests, but that does not prove that it maximises happiness.
Distinguish solvable in principle from practical with available resources. A finite search through every possible allocation may produce the best valid answer, yet take too long for millions of combinations. Missing or inaccurate inputs also constrain the result. An algorithm cannot infer that a court is broken if this fact is absent from its data.
Recognise the underlying task
Problem recognition identifies the actual task and its constraints from the scenario, rather than treating a reported symptom as the specification. Similar underlying tasks can appear in different settings: finding a vacant court and finding an unoccupied laboratory both involve matching requests to resources and detecting time conflicts.
Suppose a delivery office reports “drivers keep returning to the depot”. Possible causes include missing parcels, insufficient vehicle capacity or a poor route order. A route algorithm will not fix an inaccurate parcel list. Establish what happens, what users need and what information is available before choosing a method.
A useful statement identifies inputs, outputs, constraints and success conditions. For a parcel-loading task: inputs are parcel identifiers and positive masses, plus a vehicle capacity; output is a selected list and its total mass; the total must not exceed capacity and no parcel may be selected twice. “Select as much mass as possible” differs from “select as many parcels as possible”. For masses 6, 4 and 3 with capacity 7, the first objective chooses 4+3=7; both objectives accept two parcels here, but their preferences need not agree on other data.
Test recognition with an edge case. If there are no parcels, an empty selection of mass 0 is meaningful. If no parcel fits, returning “no selection” is better defined than inventing a parcel. If negative masses are not permitted, decide where validation rejects them. These are requirements, not details to guess after coding.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account