3.1.1 - Algorithms, decomposition and abstraction
A computer needs a clear method for completing a task. Before writing a program, decide the steps, break a large problem into manageable tasks and keep the information that matters.
Algorithms and programs
An algorithm describes the steps needed to complete a task. It is the method that a program will implement.
Algorithm
A sequence of steps to complete a task.
Suppose a club sells tickets for £4 each. A method for finding the total price is:
- Obtain the number of tickets.
- Multiply that number by 4.
- Display the total price.
These steps are precise enough to follow for different bookings. For three tickets, the calculation is 3 × 4 = £12. For five tickets, the same method gives £20. A statement such as “calculate a sensible price” would leave the important calculation undecided.
We can express the method in pseudocode, a readable description of an algorithm:
tickets ← USERINPUT
total ← tickets * 4
OUTPUT total
USERINPUT obtains a value. The arrow assigns a value to a named variable: total ← tickets * 4 calculates the expression on the right and stores its result in total. OUTPUT displays a result. The value of tickets is assumed to be a valid whole number for this example.
A program implements these steps in a programming language. Python uses = for assignment and print(...) for output; another language can implement the same algorithm using different syntax. Changing the language need not change the method. An algorithm can also be followed without a computer, as when a person uses the three steps to calculate a booking.
The Python Study demonstration below fixes the input at three tickets so that you can examine the calculation without typing an input. It implements the same method. The written examination question that follows asks for pseudocode and has no Run button.
Python demonstration: ticket total
{"code":"tickets = 3\nunit_price = 4\ntotal = tickets * unit_price\nprint(total)\n","instructions":"Predict the total before running. Run and compare it with your prediction. Change only tickets = 3 to tickets = 5, predict the new total, then run again. Explain which value changed and why the algorithm still works."}
Breaking a problem into tasks
Decomposition makes a large problem easier to solve by separating it into smaller subproblems, each with an identifiable task.
Decomposition
Breaking a problem into smaller, more manageable subproblems.
A complete ticket-booking system does more than multiply a price. It must find out what the customer wants, check availability, calculate the charge, handle payment and issue a booking confirmation. These are useful subproblems because each has a clear job and a result that other tasks can use.
| Subproblem | Identifiable task or result |
|---|---|
| Obtain the booking request | Establish the event and number of tickets wanted |
| Check availability | Decide whether enough seats remain for that event |
| Calculate the charge | Return the amount due for an accepted request |
| Handle payment | Establish whether payment succeeded |
| Confirm the booking | Record the seats sold and issue the booking reference |
The order matters. The system should not issue a successful booking confirmation before availability and payment have been checked. Defining what each task receives and produces helps the tasks fit together.
A subproblem can be decomposed further. “Check availability” might become: find the event record; read its remaining-seat count; compare that count with the requested quantity; return available or unavailable. The charge calculation from the first part is one small algorithm within the larger system.
Decomposition is useful because you can reason about, develop and test each identifiable task separately. Dividing a description into arbitrary equal-sized pieces does not necessarily produce useful subproblems: the boundaries should follow what the system needs to accomplish.
Keeping relevant detail
Abstraction reduces complexity by removing detail that is unnecessary for solving the problem, while preserving the information the solution needs.
Abstraction
Removing unnecessary detail while keeping the relevant information needed to solve a problem.
For the club's ticket-price calculation, the number of tickets and the price per ticket matter. The colour of the customer's coat does not affect the charge, so it can be left out of that model. If the club later introduces different prices for children and adults, the ticket categories become relevant and must be retained. Relevance depends on the problem you are trying to solve.
A delivery-route program provides another example. It can model roads as connections between places, with distances and permitted directions. It need not reproduce the colour of every building along a road. However, removing a one-way restriction could produce a route the driver cannot legally follow. Abstraction must simplify the problem without discarding information needed for a correct solution.
Decomposition and abstraction can be used together. Decomposition identifies a route-planning subproblem within a larger delivery system. Abstraction then chooses the road information that this subproblem needs. The first separates tasks; the second selects relevant detail within a task.
Plan the method, divide a large problem into useful tasks and retain the detail each task needs. A program then implements the resulting algorithm.