Computational methods: solvable problems, problem recognition, decomposition, and divide and conquer

Overview

Recall questions on features that make a problem solvable or unsolvable by computational methods, problem recognition, problem decomposition, divide and conquer, binary search comparisons, and algorithms that divide and combine.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What features make a problem solvable by computational methods?

   Model answer

   It can be stated precisely, with the inputs, the required processing and the expected outputs all identifiable. It can be broken down into smaller sub-problems that can each be solved. Its solution can be expressed as a finite sequence of unambiguous steps that is guaranteed to terminate — that is, as an algorithm. The data involved can be represented in a form a computer can store and manipulate, and that data can actually be obtained. Detail can be abstracted away without destroying the problem. There is a way of telling whether an answer is right, so the solution can be tested. And usually the work is repetitive, high in volume or arithmetically heavy, so a computer's speed and consistency give a genuine advantage over doing it by hand.

2. 2

   What features make a problem NOT solvable by computational methods? Give an example of each.

   Model answer

   No precise rules can be stated: 'choose the most beautiful painting in this gallery' rests on taste, with no agreed criteria to turn into steps. The problem needs human judgement, ethics or emotion: deciding whether a defendant deserves mercy, or comforting a bereaved relative. The necessary data cannot be obtained or measured: predicting one named person's exact lifespan needs facts nobody can collect. The number of possibilities is so large that even a correct algorithm could not finish in any useful time, so no exact answer is available in practice. And some problems have no algorithm at all, however much time is allowed. Separately, a problem may be technically solvable but not worth solving computationally, where a person could do it faster and more cheaply than the system would cost to build.

3. 3

   What does problem recognition involve, and why do projects so often get it wrong?

   Model answer

   Recognising that there is a problem, and then establishing what the real problem is: its scope, who is affected, what the inputs and required outputs are, and what would count as a solution. It involves gathering evidence — interviewing users, observing the current system, examining existing documents and data — rather than accepting the first description offered. Projects get it wrong by fixing the symptom instead of the cause. 'The website is slow' might really be one unindexed database query, an overloaded server only at 5pm, or oversized images; buying a faster server solves nothing if a query is the cause. Recognition also has to identify which parts are genuinely computational, since automating a badly designed process only makes it fail faster.

4. 4

   A school says 'our library keeps losing books'. What would problem recognition produce here, before anyone designs a system?

   Model answer

   It would establish the facts first: how books are currently taken out and returned, how many actually go missing each term, and whether they are lost, stolen, never returned or simply mis-shelved; whether any of this is recorded at present; who is involved; and what data already exists that could be used. The output is a precise statement of the problem — for example 'there is no record linking a borrowed book to a borrower, and no reminder when a loan becomes overdue' — together with the required inputs (book identifier, borrower identifier, date), the required outputs (a loan record, an overdue list) and the criteria by which success will be judged. If the real cause turned out to be mis-shelving, a computerised loans system would not have helped at all, which is precisely what recognition exists to catch.

5. 5

   What is problem decomposition, and how do you know when to stop decomposing?

   Model answer

   Breaking a problem into smaller sub-problems, and breaking those into smaller ones again, until each remaining piece is simple enough to be fully understood, solved and written as a single subroutine. You stop when a piece can be coded and tested directly without further planning, or when it matches something that already exists and can simply be reused. The structure that results is the structure of the program: each lowest-level sub-problem becomes a module, the modules can be shared among a team, and each can be tested on its own before the whole is assembled.

6. 6

   Decompose 'a system to run a school sports day' far enough to show what the modules would be.

   Model answer

   At the top: manage events, manage competitors, record results, produce reports. Manage events breaks into create an event, set its time and place, set the maximum number of entries. Manage competitors breaks into add a competitor, enter a competitor for an event, check eligibility. Record results breaks into enter a time or distance, validate it, rank the entries in an event, award points to the competitor's house. Produce reports breaks into per-event results, house totals, and certificates. Ranking breaks further into sort the entries and handle ties. Each of the lowest pieces — validate a time, sort entries, total by house — is small enough to be written and tested as a single subroutine, which is the signal that decomposition has gone far enough.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.